title: Universal container conversion? if from Foldable to Alternative?
body: <p>For <code>instance Alternative []</code>, <code>(&lt;|&gt;) = (++)</code>. So I regarded <code>(&lt;|&gt;)</code> as some kind of splicer, resulting in seemingly almost-universal container converter:</p>
  
  <pre><code>-- (&lt;|&gt;) = generalization of (++)
  
  (&lt;|) :: Alternative f =&gt; x -&gt; f x -&gt; f x
  x &lt;| xs = pure x &lt;|&gt; xs
  
  conv :: (Foldable t, Alternative f) =&gt; t x -&gt; f x
  conv = foldr (&lt;|) empty
  </code></pre>
  
  <p>Indeed, I was able to generalize <em>all</em> functions from <code>Data.List</code>, here's some:</p>
  
  <pre><code>-- fmap = generalization of map
  
  reverse :: (Foldable t, Alternative f) =&gt; t a -&gt; f a
  reverse = getAlt . getDual . foldMap (Dual . Alt . pure)
  
  -- asum = generalization of concat
  
  asumMap :: (Foldable t, Alternative f) =&gt; (a -&gt; f b) -&gt; t a -&gt; f b -- generalization of concatMap
  asumMap f = getAlt . foldMap (Alt . f)
  
  splitAt :: (Foldable t, Alternative f, Alternative g) =&gt; Int -&gt; t a -&gt; (f a, g a)
  splitAt n xs = let (_,fs,gs) = foldl' (\(i,z1,z2) x -&gt; if 0 &lt; i then (i-1,z1 . (x &lt;|),z2) else (0,z1,z2 . (x &lt;|))) (n,id,id) xs in (fs empty,gs empty)
  </code></pre>
  
  <p>Also, this analogy makes some interesting new instances, such as a working applicative functor for functor sums (<code>Data.Functor.Sum</code>):</p>
  
  <pre><code>instance (Foldable f, Applicative f, Alternative g) =&gt; Applicative (Sum f g) where
      pure = InL . pure
      InL f &lt;*&gt; InL x = InL (f &lt;*&gt; x)
      InL f &lt;*&gt; InR x = InR (conv f &lt;*&gt; x)
      InR f &lt;*&gt; InL x = InR (f &lt;*&gt; conv x)
      InR f &lt;*&gt; InR x = InR (f &lt;*&gt; x)
  
  instance (Foldable f, Applicative f, Alternative g) =&gt; Alternative (Sum f g) where
      empty = InR empty
      InL x &lt;|&gt; _ = InL x
      InR _ &lt;|&gt; InL y = InL y
      InR x &lt;|&gt; InR y = InR (x &lt;|&gt; y)
  </code></pre>
  
  <p>Is it actually good idea to generalize <em>all</em> functions and make new instances with this analogy, especially for list operations?</p>
  
  <p>EDIT: I'm especially concerned about ambiguous return type. For normal list operations, the return type is deducible from its argument types. But the "universal" version is not, as the return type must be explicitly specified. Is this problem severe enough to regard the analogy dangerous? (Or is there any other problem?)</p>
  
  <p>EDIT 2: If I'm understanding the behavior of <code>foldl'</code> exactly, the time complexity of universal <code>splitAt</code> (shown above) must be <code>Θ(length xs)</code>, as <code>foldl'</code> is strict for every elements, right? If yes, that must be a problem, as it's inferior to the regular version's <code>Θ(min n (length xs))</code>.</p>