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

Martijn van Steenbergen 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