Как сделать экземпляр Applicative определенного типа данных - PullRequest
Новая
       44

Как сделать экземпляр Applicative определенного типа данных

3 голосов
/ 15 октября 2019

Я читаю книгу Грэма Хаттона о Хаскелле, и не знаю, как выполнить одну часть упражнения. Упражнение говорит следующее:

Учитывая следующие выражения типов 

data Expr a = Var a | Val Int | Add (Expr a) (Expr a) deriving Show

, которые содержат переменные некоторого типа a, покажите, как превратить этот тип в экземпляры классов Functor, Applicative и Monad. С помощью примера объясните, что делает оператор >>= для этого типа.

У меня возникли проблемы с определением оператора <*> Applicative. Тип <*>: 

(<*>) :: Expr (a -> b) -> Expr a -> Expr b

Я не понимаю, как может работать (Val n) <*> mx, потому что теоретически мне нужно предоставить Expr b, но все, что у меня есть, это Expr a инет функции для преобразования (a -> b).

Я также не понимаю, что делать в случае (Add l r) <*> mx.

Это моя реализация. 

instance Functor Expr where
    --fmap :: (a -> b) -> Expr a -> Expr b
    fmap g (Var x) = Var (g x)
    fmap g (Val n) = Val n
    fmap g (Add l r) = Add (fmap g l) (fmap g r)


instance Applicative Expr where
    --pure :: a -> Expr a
    pure = Var

    -- <*> :: Expr (a -> b) -> Expr a -> Expr b
    (Var g) <*> mx = fmap g mx
    --(Val n) <*> mx = ???
    --(Add l r) <*> mx = ???

instance Monad Expr where
    -- (>>=) :: Expr a -> (a -> Expr b) -> Expr b
    (Var x) >>= g = g x
    (Val n) >>= g = Val n
    (Add l r) >>= g = Add (l >>= g) (r >>= g)


expr = Add (Add (Var 'a') (Val 4)) (Var 'b')

Наконец, у меня есть сомнения относительно >> = в монаде. Идея этого оператора заключается в том, чтобы делать такие вещи, как подстановка переменных? Нравится: 

expr >>= (\x -> if x == 'a' then Val 6 else Var x) >>= (\x -> if x == 'b' then Val 7 else Var x)

Ответы [ 3 ]

5 голосов
/ 15 октября 2019

Как вы правильно заметили, в случае: 

(Val n) <*> mx = ???

у вас есть: 

Val n :: Expr (a -> b)
mx :: Expr a

и вам необходимо произвести Expr b. Вы помните случай: 

fmap g (Val n) = ???

, когда у вас было: 

g :: a -> b
Val n :: Expr a

, и вам нужно было произвести Expr b? Вы нашли решение там.

Для случая: 

(Add l r) <*> mx

у вас есть: 

l :: Expr (a -> b)
r :: Expr (a -> b)
mx :: Expr a

, и вам нужно получить Expr b. Если бы только у вас была какая-то функция, которая могла бы взять l и mx и создать Expr b. Такая функция, если бы она существовала, вероятно, имела бы подпись: 

someFunc :: Expr (a -> b) -> Expr a -> Expr b

Конечно, с someFunc l mx и someFunc r mx, оба типа Expr b, было бы стыдно использовать только одну,Если бы был какой-то способ построить и Expr b из двух Expr b частей, это действительно было бы коленями пчел.

3 голосов
/ 15 октября 2019

Вы немного неправильно указали, какие типы доступны в случае Val n. У вас нет Expr a, а скорее Expr (a -> b), и вообще нет a или b (и даже не функция из a -> b, потому что Val содержит только Int). На самом деле, этот случай прост , потому что у вас нет полезных значений: единственное, что вы могли бы сделать, - это создать вывод, используя конструктор Val, потому что у вас нет способа сфабриковать b из воздуха. Тип Val может специализироваться на Val :: Int -> Expr b, и, к счастью, у вас есть Int валяется, поэтому вы можете написать: 

(Val n) <*> mx = Val n
3 голосов
/ 15 октября 2019

Когда вы определили pure и (>>=), одним из возможных определений (<*>) будет 

(<*>) = Control.Monad.ap

, где ap определено в стандартной библиотеке как 

ap :: Monad m => m (a -> b) -> m a -> m b
ap mf mx = do
  f <- mf
  x <- mx
  pure (f x)

На самом деле любое определение (<*>) должно быть эквивалентно этому, если существует экземпляр Monad.

...