[Haskell-cafe] beginner's problem about lists

[Henning Thielemann]

On Tue, 10 Oct 2006, Henning Thielemann wrote:

> 
> On Tue, 10 Oct 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.
> > 
> > Again it's ok for shorter [2..] [3..] to return whatever that can solve
> > the above problem correctly.
> > An infinite list could work, I guess, but I don't know how.
> 
> With PeanoNumbers,
>    http://darcs.haskell.org/htam/src/Number/PeanoNumber.hs
>  I would first attach a lazy length information to each list before any
> call to 'shorter', then I would remove this information after the last
> call to 'shorter'.
> 
> Untested code follows:
> 
> attachLength :: [a] -> (PeanoNumber.T, [a])
> attachLength xs = (genericLength xs, xs)
> 
> detachLength :: (PeanoNumber.T, [a]) -> [a]
> detachLength = snd 
> 
> shorter :: (PeanoNumber.T, [a]) -> (PeanoNumber.T, [a]) -> (PeanoNumber.T, [a])
> shorter (xl,xs) (yl,ys) = (min xl yl, if xl < yl then xs else ys)


Ah, here is a simpler solution:

compareLength :: [a] -> [b] -> Ordering
compareLength (_:xs) (_:ys) = compareLength xs ys
compareLength []     []     = EQ
compareLength (_:_)  []     = GT
compareLength []     (_:_)  = LT

shorter :: [a] -> [a] -> [a]
shorter xs ys =
   let lt = compareLength xs ys == LT
   in  zipWith (\x y -> if lt then x else y) xs ys


zipWith returns the length of the shorter list lazily and the elements are
chosen after the shortest list is determined.