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

ProgramBox

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

Post author:admin
Запись опубликована:13 мая, 2023
Post category:Вопросы по программированию

#haskell #functor

#haskell #функтор

Вопрос:

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

 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 ???

1. Первая часть проста: Baz это изделие двух типов, поэтому вам просто нужно сопоставить шаблон на Baz s g (где g :: Qux -> Foo a ). Что делать с g — это сложная часть 🙂

2. Как часто бывает в Haskell, способ думать об этом — просто «следовать типам». У вас есть функция f :: a -> b , функция (которую я вызову g ) типа Qux -> Foo a , и вам нужна функция типа Qux -> Foo b . Я почти уверен, что есть только один способ сделать это с тем, что у вас есть здесь — и чтобы увидеть это, не бойтесь использовать рекурсию 😉

Ответ №1:

Давайте начнем с заполнения левой части этого уравнения. Мы можем написать 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)

Ответ №2:

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

 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 . Если вам нужно создать функцию, lambda является незаменимым инструментом (есть и другие, но lambda — это дедушка). Итак, создайте лямбда:

 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 рекурсивно¹, мы можем создать требуемое Foo b .

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

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