[Haskell-cafe] beginner's problem about lists
Henning Thielemann
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
> 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 [()].
More information about the Haskell-Cafe
mailing list