Haskell binary tree parsing

Question

I am learning about building and parsing binary trees in Haskell and I found a program example that I can't quite understand how works.. So the code is:

module Main where

data TTT aa = Leaf [aa] | Node (TTT aa) (TTT aa)  deriving (Show,Eq);

a :: Num a => Integer -> Integer; 
a x = x^2; 

ff_a :: TTT Integer -> TTT Integer; 
ff_a t = mm a t; 

mm :: (Integer -> Integer) -> TTT Integer -> TTT Integer; 
mm f (Node a1 a2) = Node(mm f a1) (mm f a2); 
mm f (Leaf n) = Leaf(new_mm f n); 

new_mm :: (Integer -> Integer) -> [Integer] -> [Integer]; 
new_mm f (a:a1) = f a : new_mm f a1; 
new_mm f [] = []; 

tree =   
    Node   
        (Node   
            (Node   
                ((Leaf[16,-5,19]))
                ((Leaf[14,24,-55,27]))
            )  
            (Node   
                ((Leaf[37,11,64]))
                ((Leaf[-14,6,29]))
            )  
        )  
        (Node   
            (Node   
                ((Leaf[10,-19,22]))
                ((Leaf[3,4,5,-7]))
            )  
            (Node   
                ((Leaf[31,29,13]))
                ((Leaf[18,38,-4]))
            )  
        )  


main :: IO ();

t0 = tree      
t1 = ff_a tree 

main = do

    print t0;
    print t1;

Could someone explain to me how really functions mm and new_mm work? And what does Integer -> Integer and TTT integer -> TTT integer means and what data type is that?

new_mm is by definition equal to the function map. The type signature however is restricted to Integer. mm seems to be a variant of map, working for the TTT definition of binary trees (which have list leaves). — user3389669
– user3389669, Commented Jan 23, 2020 at 8:56
In case you would like to learn more about algebraic data types, which is given here by the data TTT aa = ... definition, I recommend to read the relevant section of Learn You a Haskell for Great Good. — user3389669
– user3389669, Commented Jan 23, 2020 at 9:01

Mark Seemann · Accepted Answer · 2020-01-23 09:04:20Z

The code as shown in the OP doesn't compile, but it's fairly easy to fix. Change a to:

a :: Integer -> Integer; 
a x = x^2;

(BTW, the semicolons are redundant and should be removed. It's not idiomatic Haskell to end each line with a semicolon.)

Could someone explain to me how really functions "mm" and "new_mm" work?

mm depends on new_mm, so let's start there. A common way to get a sense of how and what Haskell code does is to experiment with it in GHCi.

*Main> new_mm a []
[]
*Main> new_mm a [1,2,3]
[1,4,9]
*Main> new_mm (\i -> i + 1) [1,2,3]
[2,3,4]

The new_mm function translates each value in the input list according to a function argument. It's just the built-in map function implemented from scratch and restricted to work only on Integer. If you need to understand how the map implementation works, I'm sure that your Haskell learning resource contains an explanation.

The mm function just 'elevates' the mapping function to work on the TTT data structure.

*Main> mm a (Leaf [])
Leaf []
*Main> mm a (Leaf [1,2,3])
Leaf [1,4,9]
*Main> mm (\i -> i + 1) (Leaf [1,2,3])
Leaf [2,3,4]
*Main> mm (\i -> i + 1) (Node (Leaf [1,2,3]) (Leaf [4,5,6]))
Node (Leaf [2,3,4]) (Leaf [5,6,7])

And what does Integer -> Integer and TTT integer -> TTT integer means and what data type is that?

Integer -> Integer indicates a function that takes an Integer as input and which return an Integer.

TTT Integer -> TTT Integer (notice that I changed the case), likewise, means a function that takes a TTT Integer value as input and which returns a TTT Integer value.

Collectives™ on Stack Overflow

Haskell binary tree parsing

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related