[Haskell-cafe] beginner's problem about lists
lemming at henning-thielemann.de
Tue Oct 10 09:01:24 EDT 2006
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
> 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.
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)
(shorter (attachLength [1..5])
(shorter (attachLength [2..])
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
More information about the Haskell-Cafe