Hier de uitwerking van het tweede onderdeel van opgave 9.1

Gevraagd: definitie van toR met behulp van accumulatie.

Eerst zoeken we een patroon.

toR (Fork lt rt) = Node a (rs ++ [r]) 
                   where  Node a rs = toR lt
                                  r = toR rt

We doen nu achtereenvolgens de volgende truken:
  1. Vervang [r] door een variabele ss (dit wordt een extra argument van de
     gegeneraliseerde functie).
     Hiermee verdwijnt het tweede deel van de `where':
       Node a (rs ++ ss)
       where  Node a rs = toR lt
  2. Omdat rt nu apart als argument staat in de vorm ss (= toR rt)
     hebben we als argumenten alleen lt en ss nodig.
De gegeneraliseerde functie wordt dus (GEN)
  gtoR lt ss = Node a (rs ++ ss)
               where Node a rs = toR lt,
waar lt een Btree A is en ss een lijst van Rose A's, dus 
  gtoR :: Btree A -> [Rose A] -> Rose A.

Instantie zoeken voor toR:
  We willen dat   toR (Leaf a) = g (Leaf a) ss   voor zekere ss : [Rose A].
  Uitwerken levert dat
    toR (Leaf a)  =  Node a [],
    gtoR (Leaf a) ss  =(GEN)  Node a (rs ++ ss) 
                              where Node a rs = toR (Leaf a)
                      =  Node a (rs ++ ss)  where Node a rs = Node a []
                      =  Node a ([] ++ ss)
                      =  Node a ss
  Dus de instantie is 
    toR bt = g bt [].

Nu met staartrecursie de definitie van gtoR vinden:

  gtoR (Leaf a) ss  =(GEN)  Node a (rs ++ ss)
                            where Node a rs = toR (Leaf a)
                    =  Node a (rs ++ ss)  where Node a rs = Node a []
                    =  Node a ([] ++ ss)
                    =  Node a ss

  gtoR (Fork lt rt) ss  =(GEN)  Node a (rs ++ ss)
                                where Node a rs = toR (Fork lt rt)

                        =  Node a (rs ++ ss)
                           where Node a rs = Node a' (rs' ++ [r])
                                             where Node a' rs' = toR lt
                                                             r = toR rt

                        =  (seeing that  a = a'  and  rs = rs' ++ [r])
                           Node a' ((rs' ++ [r]) ++ ss)
                           where Node a' rs' = toR lt
                                           r = toR rt

                        =  Node a' ((rs' ++ [toR rt]) ++ ss)
                           where Node a' rs' = toR lt

                        =  Node a' (rs' ++ ([toR rt] ++ ss))
                           where Node a' rs' = toR lt

                        =(GEN) g lt ([toR rt] ++ ss)

Dus staartrecursieve definitie van toR luidt
    toR bt = g bt []
en
    gtoR (Leaf a) ss = Node a ss
    gtoR (Fork lt rt) ss = g lt ([toR rt] ++ ss)

Groeten,

Roel.