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

Twan
```