Can't figure out how to merge two lists in the following way in Haskell:
INPUT: [1,2,3,4,5] [11,12,13,14]
OUTPUT: [1,11,2,12,3,13,4,14,5]
This would work similar to shuffling a deck of cards. Thanks in advance.
views:
212answers:
4
+12
A:
merge :: [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) = x : y : merge xs ys
andri
2010-10-14 23:50:47
+5
A:
EDIT: Take a look at Ed'ka's answer and comments!
Another possibility:
merge xs ys = concatMap (\(x,y) -> [x,y]) (zip xs ys)
Or, if you like Applicative:
merge xs ys = concat $ getZipList $ (\x y -> [x,y]) <$> ZipList xs <*> ZipList ys
danlei
2010-10-15 11:08:00
Yea, to bad, that only works on equal-length lists.
Jevgeni Bogatyrjov
2010-10-15 16:55:00
+6
A:
So why do you think that simple (concat . transpose) "is not pretty enough"? I assume you've tried something like:
merge :: [[a]] -> [a]
merge = concat . transpose
merge2 :: [a] -> [a] -> [a]
merge2 l r = merge [l,r]
Thus you can avoid explicit recursion (vs the first answer) and still it's simpler than the second answer. So what are the drawbacks?
Ed'ka
2010-10-15 12:08:05
Ah, I forgot about transpose, and missed the comment. Very nice, +1 (But I wouldn't necessarily say that it's much easier than my first solution.)
danlei
2010-10-15 13:53:17
Agree. Your solution is probably even more straightforward.. The real problem with it though is that it isn't 100% correct: for the lists of different lengths (like in the sample input from the question) it doesn't work as expected (tailing '5' is missing).
Ed'ka
2010-10-15 14:03:53
Good catch! I overlooked the 5 in the sample output. I'll update my answer with a pointer to your answer and comments. Thanks!
danlei
2010-10-15 15:50:59
Correct me if I'm wrong, but while the efficiency of the algorithm in the accepted answer is O(n), the "concat . transpose" method efficiency is O(n^2) ? Also I thought that it would be better to get through the problem without importing the additional Modules (List) ?
Jevgeni Bogatyrjov
2010-10-15 16:45:36
Looks like both are O(n) although explicit recursion is more than 2 times faster and space efficient against Data.List implementation (which is expected - the latter generates lots of intermediate lists) with "ghc -O2". However I suspect the difference would be less obvious should, say, 'stream-fusion' implementation of "transpose" and "concat" be used.
Ed'ka
2010-10-15 18:16:29
The main drawback is that the average person looking at it will have to stare at it and think for a while to understand why it works, whereas the other solutions are immediately obvious. Your solution is very elegant though.
Yitz
2010-10-21 17:48:30
+2
A:
I want to propose a lazier version of merge:
merge [] ys = ys
merge (x:xs) ys = x:merge ys xs
For one example use case you can check a recent SO question about lazy generation of combinations.
The version in the accepted answer is unnecessarily strict in the second argument and that's what is improved here.
Daniel Velkov
2010-10-21 12:01:41
Well, that puts all of the elements of ys at the end, so it doesn't work. But I think what you meant was to reverse the order of the first two equations in andri's solution.
Yitz
2010-10-21 17:44:13
No, it does the same thing - alternates between each list. Notice that `xs` and `ys` are swapped in the recursive call.
Daniel Velkov
2010-10-21 18:25:29
It's a great solution! I wish I could think of something like that myself
Jevgeni Bogatyrjov
2010-10-21 23:01:24