Another fold question

[Derek Elkins]

On Thu, 06 Nov 2003 04:27:31 +0000
"Patty Fong" <patty_jf at hotmail.com> wrote:

> Having struglled over this for the better part of a day and only
> becoming more frustrated the more i try to understand it, i once again
> seek help :)
> 
> I understand how basic folds work, i.e foldr replaces (:) with some 
> parameter and [] by another i.e
> foldr (+) 0 [1,2,3] becomes 1+(2+(3+0))
> 
> I also understand how to write my own fold function. What i don't
> understand quite is how to use them. given this data type and this
> fold function i 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.  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??

Because (+) :: Num a => a -> a -> a and that's definitely not Pitch ->
Octave -> Duration -> a.  But all functions will need to return
the same type.  Once you apply all five functions to foldMusic the
result will be a function with type Music -> a (well, what a was bound
to).  Since that function can be applied to any particular constructor
of Music then the function that will replace a particular constructor
needs to return the same type as the others.

> 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)

You can use \_ _ _ -> 0 instead of nested lambdas.

> it appears to work, i think. Yet i'm still not certain of how it does
> so.
> 
> This confuses me,
> Is there anyway to represent other fold functions in a tree like 
> representation as foldr (+) 0 would appear as such?
>     +
>    1 \
>       +
>      2 \
>         +
>        3 \
>           0

All datatypes can be represented in a tree-like (graph-like actually)
way and folds follow the structure of the type(s) that they fold over. 
So for Music a particular instance might look like,

                    Tempo (2%1)
                        |   
                     PlayerPar
                    /         \
               PlayerSeq    Note ...
              /          \
            Note ...   Silence (3%4)
folds in general work from the "leaves" of the datatype to the root. 
Or another way, for more mathematically inclined people, is that folds
follow (are) the induction principle of the datatype, it works from base
case to inductive cases.  A still third way of thinking about it is that
a datastructure is an AST (abstract syntax tree) for some language and
that a fold (applied to it's parameters) is an intepreter for that
language.  So for example, you likely want to play the music so you
might have a function like,
playMusic = foldMusic playNote pause playPar playSeq changeTempo

playMusic then interprets a Music data structure as sound.  Another
"interpreter" you might want is something that lays out the music, so
you might have,
printMusic = foldMusic drawNote 
                       drawRest
                       overlapDrawing
                       nextBar
                       drawTimeSignature
printMusic interprets a Music data structure as say a pdf of sheet
music.