[Haskell-cafe] A small puzzle: inTwain as function of foldr

Ketil Malde ketil at malde.org
Fri Jun 5 07:58:43 EDT 2009


Martijn van Steenbergen <martijn at van.steenbergen.nl> writes:

>> inTwain as = let (x,y,_) = foldr (\a (r,s,t) -> case (t) of
>> {b:(b':bs) -> (r,a:s,bs); _ -> (a:r,s,t)}) ([],[],as) as in (x,y)

> This one is very interesting.

Yes, neat.

> I'm not too happy with the whole list as part of the initial
> state. That feels like cheating to me--although I obviously failed to
> specify this in my original question. 

Can you avoid it?  If you only allow one traversal of the input (and
I think the above might qualify as two, albeit simultaneous), how do
you know when you're halfway through?

I seem to remember one example case that regular languages can't solve
is a^nb^n -- is this for the same (or a related) reason?

-k
-- 
If I haven't seen further, it is by standing in the footprints of giants


More information about the Haskell-Cafe mailing list