I have the following Haskell expression:
3 : [40] ++ [50] ++ 5 : [60]
I would like to know how this expression is evaluated. Which operator has a higher precedence, : or ++?
I think the result of the expression is [3,40,50,5,60], however I did this the following way:
3 : [40] ++ [50] ++ 5 : [60]
3 : [40] ++ [50] ++ [5,60]
3 : [40] ++ [50,5,60]
3: [40,50,5,60]
[3,40,50,5,60]
Is the above the correct way to evaluate the expression? Any insights are appreciated.
Both the (++) :: [a] -> [a] -> [a] and (:) :: a -> [a] -> [a] function have 5 as precedence, as we can read in the Haskell '10 report, and are right associative.
We can also obtain this data with :i in the ghci shell:
Prelude> :i (:)
data [] a = ... | a : [a] -- Defined in ‘GHC.Types’
infixr 5 :
Prelude> :i (++)
(++) :: [a] -> [a] -> [a] -- Defined in ‘GHC.Base’
infixr 5 ++This thus means that:
3 : [40] ++ [50] ++ 5 : [60]
is short for:
3 : ([40] ++ ([50] ++ (5 : [60])))
The (++) operator is implemented as:
(++) :: [a] -> [a] -> [a] (++) [] ys = ys (++) (x:xs) ys = x : xs ++ ys
The (:) is a data constructor, so that means it can not be "further evaluated".
This makes sense since it thus means that the ++ is here only applied to the tail, and hence as long as we are interested in the head, we do not need to evaluate that function. So a right associative (++) is usually cheaper than a left associative (++) although it will result in the same list.
If we thus want to evaluate the full list, it is evaluated as:
3 : ([40] ++ ([50] ++ (5 : [60])))
-> 3 : (40 : ([] ++ ([50] ++ (5 : [60]))))
-> 3 : (40 : ([50] ++ (5 : [60])))
-> 3 : (40 : (50 : ([] ++ (5 : [60]))))
-> 3 : (40 : (50 : (5 : [60])))
or more verbose:
3 : ((40: []) ++ ((50 : []) ++ (5 : (60 : []))))
-> 3 : (40 : ([] ++ ((50 : []) ++ (5 : (60 : [])))))
-> 3 : (40 : ((50 : []) ++ (5 : (60 : []))))
-> 3 : (40 : (50 : ([] ++ (5 : (60 : [])))))
-> 3 : (40 : (50 : (5 : (60 : []))))