Haskell - Пользовательский экземпляр функтора для типа данных с конструктором функции - PullRequest
Новая
       16

Haskell - Пользовательский экземпляр функтора для типа данных с конструктором функции

1 голос
/ 16 марта 2019

У меня проблемы с написанием собственного экземпляра функтора для пользовательского типа данных (который я не могу изменить).Типы данных определены как: 

data Foo a = Baz String (Qux -> Foo a) | Bar a
data Qux = None | Quux String

Моя проблема заключается в написании функтора для типа Foo.В частности, я не уверен, как правильно применить мою функцию функтора f к функции в Foo.Я думал о том, чтобы как-то вызвать функцию в конструкторе, но поскольку у меня нет Qux доступных для использования, я застрял. 

instance Functor Foo where
    fmap f (Bar a) = Bar (f a)
    fmap f (Baz s ???) = Baz s (???) -- What goes here?

    -- Clearly, something like this doesn't work
    -- fmap f (Baz s g) = Baz s (f g) 

    -- I've also tried something like this, but I'm not sure where to go from there
    -- fmap f (Baz s (None   -> Bar b)) = Baz s (f b) ???
    -- fmap f (Baz s (Quux x -> Bar b)) = Baz s ???

Ответы [ 2 ]

6 голосов
/ 16 марта 2019

Давайте начнем с завершения левой части этого уравнения.Мы можем написать g, чтобы связать вашу функцию с переменной.

fmap f (Baz s g) = Baz s (???)

Затем нам нужно заполнить вопросительные знаки другой функцией, которая принимает Qux ивозвращает Foo b.

fmap f (Baz s g) = Baz s (\q -> ???)

Мы можем сделать только одну вещь с q, которая применяется к g.

fmap f (Baz s g) = Baz s (\q -> g q)

Однако, это дает нам Foo a, но нам нужно Foo b!У нас нет функции сделать это.У нас, однако, есть f, который принимает a и возвращает b.Если бы только был способ взять a -> b и превратить его в Foo a -> Foo b ... о, подождите, это называется fmap!

fmap f (Baz s g) = Baz s (\q -> fmap f (g q))

Если выхотите написать функцию в нотации без точек (https://wiki.haskell.org/Pointfree), вы можете сделать это вместо этого.

fmap f (Baz s g) = Baz s (fmap f . g)

4 голосов
/ 16 марта 2019

Следуйте за типами: 

fmap f (Baz s g) = GOAL
   -- f    :: a -> b
   -- s    :: String
   -- g    :: Qux -> Foo a
   -- GOAL :: Foo b

Итак, мы ищем Foo b (линия ЦЕЛИ). Мы можем сделать один с Bar или Baz. fmap должен сохранить структуру, поэтому она должна быть Baz. Аргумент String для Baz, вероятно, не должен измениться, это только второй аргумент, который ставит проблему. 

fmap f (Baz s g) = Baz s GOAL
   -- f    :: a -> b
   -- s    :: String
   -- g    :: Qux -> Foo a
   -- GOAL :: Qux -> Foo b

Теперь мы должны сделать Qux -> Foo b. Если вам нужно создать функцию, лямбда - важный инструмент (есть и другие, но лямбда - это дедушка). Итак, сделайте лямбду: 

fmap f (Baz s g) = Baz s (\x -> GOAL)
   -- f    :: a -> b
   -- s    :: String
   -- g    :: Qux -> Foo a
   -- x    :: Qux          <-- NEW
   -- GOAL :: Foo b

Обратите внимание, что теперь у нас есть x :: Qux для работы. Используя g и x, мы можем сделать Foo a, а затем, используя fmap f рекурсивно 1 , мы можем сделать необходимое Foo b.

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

1 Рекурсивный тип обычно имеет соответствующее рекурсивное определение fmap. Место, в котором происходит рекурсия в fmap, точно соответствует типу рекурсии.

...