Прикладной экземпляр для непустого лиственного дерева в Haskell

Учитывая следующий тип данных:

data Tree a =
    Branch (Tree a) (Tree a)
  | Leaf a deriving (Eq, Show)

И следующий экземпляр Functor:

instance Functor Tree where
  fmap f (Leaf a)       = Leaf $ f a
  fmap f (Branch t1 t2) = Branch (fmap f t1) (fmap f t2)

Как лучше всего реализовать экземпляр Applicative для этого дерева? Я придумал:

instance Applicative Tree where
  pure = Leaf

  Leaf f       <*> t            = f <$> t
  Branch t1 t2 <*> Leaf a       = t1 <*> Leaf a
  Branch t1 t2 <*> Branch t3 t4 = Branch (t1 <*> t3) (t2 <*> t4)

Даже если он скомпилируется, я очень подозрительно отношусь к этой реализации. Я не знаю, должен ли этот Branch (Leaf (+1)) (Leaf (+2)) <*> Leaf 7 возвращать Leaf 8 (найти ближайшую функцию для применения) или дублировать и возвращать Branch (Leaf 8) (Leaf 9).


haskell binary-tree applicative
person MMacphail    schedule 15.08.2018    source источник

Ответы (1)


arrow_upward
6
arrow_downward

Даже если он скомпилируется, я очень подозрительно отношусь к этой реализации. Я не знаю, должен ли этот Branch (Leaf (+1)) (Leaf (+2)) ‹*> Leaf 7 возвращать Leaf 8 (найти ближайшую функцию для применения) или дублировать и возвращать Branch (Leaf 8) (Leaf 9)

Разумные примеры должны следовать применимым законам функтора, и один из них:

u <*> pure y = pure ($ y) <*> u -- Interchange

i.e.

Branch t1 t2 <*> Leaf a

должно быть таким же, как:

pure ($ a) <*> Branch t1 t2

Но согласно этой реализации:

Leaf f <*> t = f <$> t

Он должен быть равен:

($ a) <$> Branch t1 t2

i. e

Branch (fmap ($ a) t1) (fmap ($ a) t2)

Следовательно, в конкретном случае Branch (Leaf (+1)) (Leaf (+2)) <*> Leaf 7 он должен возвращать:

Branch (Leaf 8) (Leaf 9)
person Igor Drozdov    schedule 15.08.2018
comment
Спасибо за ваш ответ! Что означает ($ а)? - person MMacphail; 15.08.2018
comment
Ссылка, которую я предоставил (о законах), содержит следующую информацию: ($ y) — это функция, которая передает y в качестве аргумента другой функции. en.wikibooks.org/wiki/Haskell/ - person Igor Drozdov; 15.08.2018
comment
@MMacphail ($ a) аналогичен (\f -> f a) функции, которая принимает функцию f и применяет ее к a. - person chi; 15.08.2018
comment
@MMacphail, в более общем смысле, если *&* является оператором, (*&* y) (называемый разделом оператора) совпадает с \x -> x *&* y. В данном случае это оператор $, определенный f $ a = f a. Вы также можете использовать оператора на другой стороне: (x *&*) = \y -> x *&* y - person dfeuer; 15.08.2018
comment
@IgorDrozdov Верно ли последнее уравнение в авторском коде? А именно, Branch t1 t2 <*> Branch t3 t4 = Branch (t1 <*> t3) (t2 <*> t4) ... Интуитивно это кажется неправильным, а Branch t1 t2 <*> t = Branch (t1 <*> t) (t2 <*> t) чувствует себя лучше, но я не могу привести ни одного примера или доказательства, подтверждающего это чувство. - person micsza; 11.06.2019