On Tue, 10 Oct 2006 [EMAIL PROTECTED] 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) detachLength (shorter (attachLength [1..5]) (shorter (attachLength [2..]) (attachLength [3..]))) This will work with if one of the lists is finite. If all lists are infinite, this solution fails. You can simulate the peano numbers also with [()]. _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
