Почему шаблоны на Хаскеле должны быть линейными? - PullRequest
Новая
       27

Почему шаблоны на Хаскеле должны быть линейными?

4 голосов
/ 06 мая 2019

Пример запрещенного кода (который я хотел бы написать): 

isWaiting :: Eq a => a -> PriorityQueue a -> Bool
isWaiting x EmptyQueue = False
isWaiting x (Push x y p) = True 
isWaiting x (Push z y p) = isWaiting x p

Та же логика, но рабочий вариант: 

isWaiting :: Eq a => a -> PriorityQueue a -> Bool
isWaiting x EmptyQueue = False
isWaiting x (Push z y p) = if x == z then True else isWaiting x p

Ответы [ 2 ]

15 голосов
/ 06 мая 2019

Обработка нелинейных паттернов потребует определения равенства по двум совпадающим терминам.В общем, мы не можем сделать это: 

areFunctionsEqual :: (Integer->Integer) -> (Integer->Integer) -> Bool
areFunctionsEqual f f = True
areFunctionsEqual _ _ = False

Вышесказанное не может быть действительно разрешено, поскольку мы не можем сравнивать функции.

Однако можно задаться вопросом, почему это не разрешено длятипы в классе Eq, где разрешимость не является проблемой.Это позволило бы написать 

foo x y x = ...

вместо 

foo x y z | z==x = ...

Это сложнее оправдать.Кто-то может утверждать, что первый нелинейный шаблон может быть написан случайно и привносит тонкие ошибки.Второе не так уж и долго, и лучше документирует намерение.

Является ли это хорошим аргументом или нет, это вопрос личного мнения, я думаю.

Еще один тонкий аргумент:

foo x y z | z==x = bar x

денотально эквивалентно 

foo x y z | z==x = bar z

, но эти два варианта могут по-прежнему приводить к разным следам памяти, так как в более крупной программе первый из них может позволить z быть мусоромсобранный, тогда как второй позволил бы x быть собранным мусором.Если, скажем, z уже упоминается в другом месте программы, мы хотим использовать вторую форму, чтобы x собирал мусор.Первая форма привела бы к тому, что и x, и z были бы сохранены в памяти.

Если бы мы могли написать foo x y x = bar x, что будет собирать мусор?Не очень понятно.

Возможно, это очень незначительный момент, поскольку можно все же использовать явный вариант, если управление сборкой мусора так важно.

9 голосов
/ 06 мая 2019

Некоторые языки с сопоставлением с образцом (например, Prolog, Erlang) допускают, что 

isWaiting x (Push x y p) = True

означает, что шаблон соответствует только тогда, когда две переменные шаблона x эквивалентны.

Haskellне делает.Вы можете прочитать о Pattern Matching - Prolog vs. Haskell , если хотите.

Альтернатива вашему рабочему варианту, который использует охрану, выглядит следующим образом: 

isWaiting :: Eq a => a -> PriorityQueue a -> Bool
isWaiting x EmptyQueue = False
isWaiting x (Push z y p)
  | x == z = True
  | otherwise = isWaiting x p

И тот, который использует оператор (||) вместо if-then-else выглядит следующим образом: 

isWaiting :: Eq a => a -> PriorityQueue a -> Bool
isWaiting x EmptyQueue = False
isWaiting x (Push z y p) = x == z || isWaiting x p

Edit: И тот, который использует Даниэль Вагнерпредложение о выводе Foldable: 

{-# LANGUAGE DeriveFoldable #-}

type Priority = ...

data PriorityQueue a
  = EmptyQueue
  | Push a Priority (PriorityQueue a)
  deriving (Foldable)

isWaiting :: Eq a => a -> PriorityQueue a -> Bool
isWaiting = elem
...