[Haskell-cafe] beginner's problem about lists
Twan van Laarhoven
twanvl at gmail.com
Tue Oct 10 17:41:43 EDT 2006
falseep at 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..])
More information about the Haskell-Cafe