Functions of different Data Types in Haskell

Question

I have the DataType

data Rose a = Leaf a | Node [Rose a]

an example would be:

fmfp = Node [Node [Leaf "F"], Node [], Node [Leaf "F", Leaf "P"], Leaf "M"]

which graphically looks like this:

I have learned how to (mechanically) write fold functions for different data types, and so I came up with this fold function:

foldRose :: (a -> r) -> ([r] -> r) -> Rose a -> r

foldRose fl fn Leaf a = fl a
foldRose fl fn Node a = fn (map (foldRose fl fn)) a

The thing is, I don't really understand WHAT it does. For example, if I had

foldRose id concat fmfp

what would it do exactly? Would it be

foldRose id concat fmfp = concat [concat [id "F"], concat [], 
                                  concat [id "F", id "P"], id "M"]

How do you wrap your mind around those kinds of functions? What do they intuitively mean? Also, how do I write a mapRose function, what would I have to think befre starting, what would it be supposed to do?

"Would it be …" - yes, exactly that. Your intuition seems to be fine already. — Bergi
– Bergi, Commented Aug 14, 2019 at 7:23
The output is thus "FFPM", since you concatenate the labels. — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Aug 14, 2019 at 7:54
how would I write a map, what's the thinking behind it, the important things to consider before starting? — SavannahGemp
– SavannahGemp, Commented Aug 14, 2019 at 8:03
A fold (AKA catamorphism) intuitively "replaces" each constructor with a user-provided function, and computes the resulting term. I think you understand that. From a higher viewpoint, it expresses the existence of the unique morphism between an initial F-algebra and any given F-algebra, but this can be hard to understand without a proper background. Still, you might want to read about cata from recursion-schemes, or Bartosz Milewski's book if you want a deeper understanding. — chi
– chi, Commented Aug 14, 2019 at 8:12
mapRose f t replaces every value x :: a in the tree t :: Rose a with f x. The result is then a Rose b, if f :: a -> b. GHC can even generate it for you (using deriving Functor and a few extensions), but writing it manually can be a nice exercise. — chi
– chi, Commented Aug 14, 2019 at 8:15

Will Ness · Accepted Answer · 2019-08-14 13:09:09Z

Just follow the steps, slowly and confidently.

data Rose a = Leaf a | Node [Rose a]

fmfp = Node [ Node [Leaf "F"]
            , Node []
            , Node [Leaf "F", Leaf "P"]
            , Leaf "M" ]

foldRose :: 
         (a -> r)               -> 
               ([r] -> r)        -> 
                     Rose a       ->  r
foldRose fLeaf fNode (Leaf a    )  =  fLeaf a
foldRose fLeaf fNode (Node trees)  =  fNode (map (foldRose fLeaf fNode) trees)

("r" is for recursive result).

Notice that you had few errors there, which I fixed in the above. Now,

  foldRose id concat fmfp 
= let fLeaf = id
      fNode = concat
  in
  foldRose fLeaf fNode (Node [Node [Leaf "F"], Node [], Node [Leaf "F", Leaf "P"], Leaf "M"])
= fNode (map (foldRose fLeaf fNode) 
                             [Node [Leaf "F"], Node [], Node [Leaf "F", Leaf "P"], Leaf "M"])
= fNode [
          foldRose fLeaf fNode $ Node [Leaf "F"]
        , foldRose fLeaf fNode $ Node []
        , foldRose fLeaf fNode $ Node [Leaf "F", Leaf "P"]
        , foldRose fLeaf fNode $ Leaf "M" ]
= fNode [
          fNode $ map (foldRose fLeaf fNode) [Leaf "F"]
        , fNode $ map (foldRose fLeaf fNode) []
        , fNode $ map (foldRose fLeaf fNode) [Leaf "F", Leaf "P"]
        , fLeaf $ "M" ]
= fNode [
          fNode [ foldRose fLeaf fNode $ Leaf "F"]
        , fNode []
        , fNode [ foldRose fLeaf fNode $ Leaf "F", foldRose fLeaf fNode $ Leaf "P"]
        , fLeaf "M" ]
= fNode [
          fNode [ fLeaf "F"]
        , fNode []
        , fNode [ fLeaf "F", fLeaf "P"]
        , fLeaf "M" ]

and that is simply

= concat [ concat [ id "F"]
         , concat []
         , concat [ id "F", id "P"]
         , id "M"
         ]
= concat [ concat [ "F"], [], concat [ "F", "P"], "M" ]
= concat [          "F",               "FP",      "M" ]

Collectives™ on Stack Overflow

Functions of different Data Types in Haskell

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related