[Haskell-cafe] beginner's problem about lists

Tue Oct 10 09:38:51 EDT 2006

 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.