On Thu, 06 Nov 2003 04:27:31 +0000
"Patty Fong"
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.