<div dir="ltr">Um, the result is exponential in size. A problem will emerge in any solution. :)<br></div><div class="gmail_extra"><br><div class="gmail_quote">On 3 April 2016 at 05:38, David Feuer <span dir="ltr"><<a href="mailto:david.feuer@gmail.com" target="_blank">david.feuer@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Your lists are very short. Pump them up to thousands of elements each<br>
and you will see a problem emerge in the naive solution.<br>
<div class="HOEnZb"><div class="h5"><br>
On Sun, Apr 3, 2016 at 12:16 AM, Arseniy Alekseyev<br>
<<a href="mailto:arseniy.alekseyev@gmail.com">arseniy.alekseyev@gmail.com</a>> wrote:<br>
> I measure the following naive solution of interleave2 beating yours in<br>
> performance:<br>
><br>
> i2 [] ys = [ys]<br>
> i2 xs [] = [xs]<br>
> i2 (x : xs) (y : ys) =<br>
>   fmap (x :) (i2 xs (y : ys)) ++ fmap (y :) (i2 (x : xs) ys)<br>
><br>
> The program I'm benchmarking is:<br>
><br>
> main = print $ sum $ map sum $ interleavings<br>
> [[1,2,3,4],[5,6,7,8],[9,10,11,12],[1,1,1]]<br>
><br>
><br>
><br>
> On 3 April 2016 at 04:05, David Feuer <<a href="mailto:david.feuer@gmail.com">david.feuer@gmail.com</a>> wrote:<br>
>><br>
>> I ran into a fun question today:<br>
>> <a href="http://stackoverflow.com/q/36342967/1477667" rel="noreferrer" target="_blank">http://stackoverflow.com/q/36342967/1477667</a><br>
>><br>
>> Specifically, it asks how to find all ways to interleave lists so that<br>
>> the order of elements within each list is preserved. The most<br>
>> efficient way I found is copied below. It's nicely lazy, and avoids<br>
>> left-nested appends. Unfortunately, it's pretty seriously ugly. Does<br>
>> anyone have any idea of a way to do this that's both efficient and<br>
>> elegant?<br>
>><br>
>> {-# LANGUAGE BangPatterns #-}<br>
>> import Data.Monoid<br>
>> import Data.Foldable (toList)<br>
>> import Data.Sequence (Seq, (|>))<br>
>><br>
>> -- Find all ways to interleave two lists<br>
>> interleave2 :: [a] -> [a] -> [[a]]<br>
>> interleave2 xs ys = interleave2' mempty xs ys []<br>
>><br>
>> -- Find all ways to interleave two lists, adding the<br>
>> -- given prefix to each result and continuing with<br>
>> -- a given list to append<br>
>> interleave2' :: Seq a -> [a] -> [a] -> [[a]] -> [[a]]<br>
>> interleave2' !prefix xs ys rest =<br>
>>   (toList prefix ++ xs ++ ys)<br>
>>      : interleave2'' prefix xs ys rest<br>
>><br>
>> -- Find all ways to interleave two lists except for<br>
>> -- the trivial case of just appending them. Glom<br>
>> -- the results onto the given list.<br>
>> interleave2'' :: Seq a -> [a] -> [a] -> [[a]] -> [[a]]<br>
>> interleave2'' !prefix [] _ = id<br>
>> interleave2'' !prefix _ [] = id<br>
>> interleave2'' !prefix xs@(x : xs') ys@(y : ys') =<br>
>>   interleave2' (prefix |> y) xs ys' .<br>
>>       interleave2'' (prefix |> x) xs' ys<br>
>><br>
>> -- What the question poser wanted; I don't *think* there's<br>
>> -- anything terribly interesting to do here.<br>
>> interleavings :: [[a]] -> [[a]]<br>
>> interleavings = foldr (concatMap . interleave2) [[]]<br>
>><br>
>><br>
>> Thanks,<br>
>> David<br>
>> _______________________________________________<br>
>> Haskell-Cafe mailing list<br>
>> <a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
>> <a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
><br>
><br>
</div></div></blockquote></div><br></div>