[Haskell-cafe] beginner's problem about lists
falseep at gmail.com
falseep at gmail.com
Tue Oct 10 09:42:04 EDT 2006
Thanks for your reply. I tried a few ways but none worked.
One is like:
shorter as bs = f id id as bs where
f ca cb [] _ = ca []
f ca cb _ [] = cb []
f ca cb (a:as) (b:bs) = f (ca.(a:)) (cb.(b:)) as bs
However this will result in a non-terminating loop for shorter [1..] [2..],
since the first two patterns of f shall never match.
Another way, I could guarantee that the evaluation of
shorter [1..5] (shorter [1..] [2..])
terminate but I lose the information to figure out which list was the
shortest one.
Using zips:
shorter = zipWith (\a b -> undefined)
-- this returns the length, but not the content of the shorter list
(\a b -> undefined) could be replaced with something that encode the
contents of
the two lists, but it makes no difference since I won't know which one is
the answer.
The difficulty is that I cannot have these both:
A. if one list is finite, figure out the shorter one
B. if both are infinite, returning an infinite list could work
BTW, there IS an way to implement this functionality for a finite list of
(possibly infinite) lists:
shortest = measureWith [] where
measureWith ruler as = f matches
where ruler' = undefined : ruler
matches = filter p as
p a = length (zip ruler' a) == length (zip ruler a)
f [] = measureWith ruler' as
f matches = matches
which somehow makes it unnecessary to find the function "shorter",
but the original simple problem is interesting itself.
Thanks.
On 10/10/06, Neil Mitchell <ndmitchell at gmail.com> wrote:
>
> Hi,
>
> The trick is not call "length", since length demands the whole of a
> list, and won't terminate on an infinite list. You will want to
> recurse down the lists.
>
> Is this a homework problem? It's best to declare if it is, and show
> what you've managed to do so far.
>
> Thanks
>
> Neil
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20061010/988c4002/attachment.htm
More information about the Haskell-Cafe
mailing list