falseep@gmail.com wrote:
Hi all,
I'm trying to implement a function that returns the shorter one of two given lists, something like shorter :: [a] -> [a] -> [a] such that shorter [1..10] [1..5] returns [1..5], and it's okay for shorter [1..5] [2..6] to return either.
Simple, right?
However, it becomes difficult when dealing with infinite lists, for example, shorter [1..5] (shorter [2..] [3..]) Could this evaluate to [1..5]? I haven't found a proper implementation.
The trick is to make the function result lazy enough. When you take an element from both lists, you already know that the result will have the form (_:_), you just don't know what the head will be. One way to keep the head unevaluated is to return which of the lists is actually sorter:
shorter xs ys = snd (shorter' xs ys) where -- shorter' xs ys = -- (length xs < length ys, shorter xs ys) shorter' [] [] = error "same length" shorter' xs [] = (False, []) shorter' [] ys = (True, []) shorter' (x:xs) (y:ys) = (xsShorter, z:zs) where z = if xsShorter then x else y (xsShorter, zs) = shorter' xs ys
This works as expected: *Main> shorter [1..5] (shorter [2..] [3..]) [1,2,3,4,5] Twan