# Another fold question

Dean Herington heringtonlacey at mindspring.com
Thu Nov 6 00:26:55 EST 2003

```At 4:27 AM +0000 2003/11/06, Patty Fong wrote:
>
>data Music
>	= Note Pitch Octave Duration
>	| Silence Duration
>	| PlayerPar Music Music
>	| PlayerSeq Music Music
>	| Tempo (Ratio Int) Music
>data Pitch = Cf | C | Cs
>type Octave = Int
>type Duration = Ratio Int
>
>foldMusic :: (Pitch -> Octave -> Duration -> a)
>	-> (Duration -> a)
>	-> (a -> a -> a)
>	-> (a -> a -> a)
>	-> (Ratio Int -> a -> a)
>	-> Music
>	-> a
>
>foldMusic n _ _ _ _ (Note pitch octive duration) = n pitch octive duration
>foldMusic _ s _ _ _ (Silence duration) = s duration
>foldMusic n s p1 p2 t (PlayerPar partOne partTwo) = p1 (foldMusic n
>s p1 p2 t partOne)(foldMusic n s p1 p2 t partTwo)
>foldMusic n s p1 p2 t (PlayerPar partA partB) = p2 (foldMusic n s p1
>p2 t partA)(foldMusic n s p1 p2 t partB)
>foldMusic n s p1 p2 t (Tempo rate part) = t rate (foldMusic n s p1 p2 t part)
>
>I understand that when i use the foldMusic function i need to pass
>it 5 parameters.

Actually, 6 parameters are required before the function invocation is complete.

>   given the type signiature, why can i pass (+) as a parameter for
>p1 but not for n, what determines what can be passed as a parameter,
>because they all have the return type a??

A match between two function types requires not only that the return
types match, but also that there are the same number of parameters
and that the parameter types match.

>I attempted to create a function that utilises the foldMusic
>function that counts the number of notes:
>
>count_notes :: Music -> Integer
>count_notes = foldMusic (\_-> \_ -> \_ -> 1) (\_ -> 0) (+) (+) (\_ -> \_ -> 0)
>
>it appears to work, i think. Yet i'm still not certain of how it does so.

Very close.  The function for "Tempo" needs fixing.  Try the
following (untested code):

count_notes = foldMusic (\_ _ _ -> 1) (\_ -> 0) (+) (+) (\_ m -> m)

>Is there anyway to represent other fold functions in a tree like
>representation as foldr (+) 0 would appear as such?
>    +
>   1 \
>      +
>     2 \
>        +
>       3 \
>          0

Yes, but it's too late for me to draw the more complicated diagram
that would correspond to your Music example.

Dean

P.S.

At 3:41 PM +1100 2003/11/06, Thomas L. Bevan wrote:
>what you have written is not a fold. A fold operates over a list. There is no
>list in your code, only some sort of tree structure.

To me, a "fold" operates over any recursively defined (aka
"inductive") data type.  With this more general definition, what
Patty has written is most certainly a fold.  In fact, "count_notes"
above corresponds directly to Thomas's "countNotes":

>countNotes Silence _ =  0
>countNotes Note_ =  1
>countNotes PlayerPar m1 m2 =  (countNotes m1) + (countNotes m2)
>countNotes PlayerSeq m1 m2 =   (countNotes m1) + (countNotes m2)
>countNotes Tempo _ m =  countNotes m

```