[Haskell-beginners] Traverse tree with computing current level using Foldable instance.

[Chaddaï Fouché]

On Wed, May 23, 2012 at 12:51 PM, Dmitriy Matrosov <sgf.dma at gmail.com> wrote:
> On 05/22/12 06:18, Brent Yorgey wrote:
>> However, you should be able to define a general fold for Tape, with
>> type
>>
>>   foldTape :: (a ->  [b] ->  b) ->  Tape a ->  b
>>

So, you wrote it correctly :

> foldTape :: (a -> [b] -> b) -> Tape a -> b
> foldTape f (Tape x ts) = f x (map (foldTape f) ts)

This appears desperate since there's no mention of Int anywhere in
this function and the function applied stay the same whatever the
level : the initially given f parameter.
But there's a trick to this, we'll have to treat some of our type
variable like functions, here only b can vary freely (a is imposed by
the Tape a inputted), so let's see what it looks like if we make it a
functional type (with Int parameter):

> foldTape :: (a -> [Int -> b] -> (Int -> b)) -> Tape a -> (Int -> b)

much more promising wouldn't you say ? The solution now looks like that :

> foldTapeD :: (Monoid m) => (Int -> a -> m) -> Tape a -> m
> foldTapeD f t = (foldTape go t) 0
>   where
>     go x fs n = ....

I let you write your solution (if you didn't find before tomorrow
evening, I'll give you the answer).

You can then call foldTapeD thus :

> foldTapeD (\n x -> if n < 2 then [x] else []) testTape

(much nicer than your initial solution, is it not ?)
-- 
Jedaï