Haskell: порядок вычисления для операторов (++) и (:)

Question

У меня есть следующее выражение Haskell:

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]
3: [40,50,5,60]
[3,40,50,5,60]

Является ли приведенный выше правильный способ оценки выражения?Любые идеи приветствуются.

Answer 1

Обе функции (++) :: [a] -> [a] -> [a] и (:) :: a -> [a] -> [a] имеют 5 как приоритет , как мы можем прочитать в отчете Haskell '10 , и ассоциативно справа.

Мы также можем получить эти данные с помощью :i в оболочке ghci:

Prelude> :i (:)
data [] a = ... | a : [a]       -- Defined in ‘GHC.Types’
<b>infixr 5</b> :
Prelude> :i (++)
(++) :: [a] -> [a] -> [a]       -- Defined in ‘GHC.Base’
<b>infixr 5</b> ++

Таким образом, это означает, что:

3 : [40] ++ [50] ++ 5 : [60]

сокращенно от:

3 : ([40] ++ ([50] ++ (5 : [60])))

Оператор (++) реализован как :

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

(:) является конструктором данных, так что это означает, что его нельзя «дополнительно оценить».

Это имеет смысл, поскольку это означает, что ++ здесь применяется только к хвосту, и, следовательно, пока мы заинтересованы в голове, нам не нужно оценивать эту функцию. Таким образом, правая ассоциация (++) обычно дешевле, чем левая ассоциация (++), хотя это приведет к тому же списку.

Если мы хотим оценить полный список, он оценивается как:

   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])))

или более многословный:

   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 : []))))