[Haskell-cafe] beginner's problem about lists

[Twan van Laarhoven]

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..])
[1,2,3,4,5]

Twan