Объективы Haskell: как сделать вид хорошо играть с траверсом?

Question

Я пытаюсь узнать о линзах, реализуя его в Haskell. Я реализовал view комбинатор следующим образом:

{-# LANGUAGE RankNTypes #-} 

import Control.Applicative 
import Data.Traversable 

type Lens s a = Functor f => (a -> f a) -> s -> f s 

view :: Lens s a -> s -> a 
view lens = getConst . lens Const 

Однако, когда я пытаюсь использовать его в сочетании с traverse я получаю следующее сообщение об ошибке:

Prelude> :load Lens.hs 
[1 of 1] Compiling Main    (Lens.hs, interpreted) 
Ok, modules loaded: Main. 
*Main> :t view traverse 

<interactive>:1:6: 
    Could not deduce (Applicative f) arising from a use of ‘traverse’ 
    from the context (Traversable t) 
     bound by the inferred type of it :: Traversable t => t a -> a 
     at Top level 
    or from (Functor f) 
     bound by a type expected by the context: 
       Functor f => (a -> f a) -> t a -> f (t a) 
     at <interactive>:1:1-13 
    Possible fix: 
     add (Applicative f) to the context of 
     a type expected by the context: 
      Functor f => (a -> f a) -> t a -> f (t a) 
     or the inferred type of it :: Traversable t => t a -> a 
    In the first argument of ‘view’, namely ‘traverse’ 
    In the expression: view traverse 

К сожалению, я не понимаю эту ошибку сообщение. Пожалуйста, объясните, что это значит и как я могу это исправить.

Answer 1

Как и другие ответы уже объяснить, проблема в том, что view ожидает то, что работает для любого Functor f, но traverse работает только тогда, когда f также Applicative (и есть функторы, которые не являются аппликативны).

В lens, проблема решается за счет типа view не принять Rank2 аргумента (на самом деле, большинство функций в объективе не использовать тип объектива синонима, они всегда использовать что-то более слабое). Для вашей функции обратите внимание, что view использует только f ~ Const. Именно поэтому вы можете изменить тип подпись:

view :: ((a -> Const a a) -> s -> Const a s) -> s -> a 

Реализация может остаться такой же, но теперь view также работает на traverse:

view traverse :: (Traversable t, Monoid a) => t a -> a 

Обратите внимание на дополнительные Monoid ограничение. Это ограничение появляется, потому что если вы установили f ~ Const a в traverse :: (Traversable t, Applicative f) => (a -> f a) -> t a -> f (t a), вам понадобится экземпляр Applicative (Const a). У этого экземпляра есть ограничение Monoid на a. И это также имеет смысл, потому что пройденный может быть пустым или содержать более одного элемента, поэтому вам нужны mempty и mappend.

Answer 2

traverse имеет этот тип:

traverse :: (Applicative f, Traversable t) => (x -> f y) -> t x -> f (t y) 

Если мы делаем свободную переменную f в определении типа в Lens явной, ее определение на самом деле

type Lens s a = forall f . Functor f => (a -> f a) -> s -> f s 

Так view хочет функцию, которая может работать на любойFunctor, тогда как traverse может работать только на Applicative.

Вы можете исправить ошибку, просто изменив Functor на Applicative в определении Lens, но я не уверен, что именно этого вы хотели бы достичь здесь.

Answer 3

Т.Л., др - Согласно вашему определению Lens, traverse не может быть, потому что Lenstraverse не работает для всех Functor с.

---

Давайте посмотрим на ваши типы:

λ :set -XRankNTypes 
λ :m +Control.Applicative Data.Traversable 
λ type Lens s a = Functor f => (a -> f a) -> s -> f s 
λ :t traverse 
traverse 
    :: (Applicative f, Traversable t) => (a -> f b) -> t a -> f (t b) 

Теперь в этот момент мы видим, что traverse есть, в одну сторону, чуть более общим, чем наш Lens типа - это может занять функцию от a -> f b, где наш объектив может принимать только функции от a -> f a.

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

λ :t traverse :: (Traversable t, Applicative f) => (a -> f a) -> t a -> f (t a) 
traverse :: (Traversable t, Applicative f) => (a -> f a) -> t a -> f (t a) 
    :: (Applicative f, Traversable t) => (a -> f a) -> t a -> f (t a) 

Так что теперь это очевидно, что если traverse это быть Lens, он должен быть Lens (t a) a, так как это единственный способ сделать переменные типа выстраиваются в линию.

Так что давайте попробуем это.

λ :t traverse :: Lens (t a) a 

<interactive>:1:1: 
    Could not deduce (Traversable t1) arising from a use of `traverse' 
    from the context (Functor f) 
     bound by the inferred type of 
       it :: Functor f => (a -> f a) -> t a -> f (t a) 
     at Top level 
    or from (Functor f1) 
     bound by an expression type signature: 
       Functor f1 => (a1 -> f1 a1) -> t1 a1 -> f1 (t1 a1) 
     at <interactive>:1:1-24 
    Possible fix: 
     add (Traversable t1) to the context of 
     an expression type signature: 
      Functor f1 => (a1 -> f1 a1) -> t1 a1 -> f1 (t1 a1) 
     or the inferred type of 
      it :: Functor f => (a -> f a) -> t a -> f (t a) 
    In the expression: traverse :: Lens (t a) a 

Oof, ему это не понравилось. Ой, подождите, чтобы использовать traverse наш тип t должен быть Traversable, поэтому давайте добавим это ограничение.(Так же, как «Возможное исправление») предлагает:

λ :t traverse :: Traversable t => Lens (t a) a 

<interactive>:1:1: 
    Could not deduce (Applicative f1) arising from a use of `traverse' 
    from the context (Functor f, Traversable t) 
     bound by the inferred type of 
       it :: (Functor f, Traversable t) => (a -> f a) -> t a -> f (t a) 
     at Top level 
    or from (Traversable t1, Functor f1) 
     bound by an expression type signature: 
       (Traversable t1, Functor f1) => 
       (a1 -> f1 a1) -> t1 a1 -> f1 (t1 a1) 
     at <interactive>:1:1-41 
    Possible fix: 
     add (Applicative f1) to the context of 
     an expression type signature: 
      (Traversable t1, Functor f1) => 
      (a1 -> f1 a1) -> t1 a1 -> f1 (t1 a1) 
     or the inferred type of 
      it :: (Functor f, Traversable t) => (a -> f a) -> t a -> f (t a) 
    In the expression: traverse :: Traversable t => Lens (t a) a 

Итак, теперь проблема в том, что он не может сделать вывод, что f является Applicative (который также необходимо использовать traverse), так что это Functor (который он получает от определения Lens).

Мы не можем добавить Applicative f в контекст, хотя - f скрыт. Когда мы говорим type Lens s a = Functor f => (a -> f a) -> s -> f s, мы говорим, что Lens должен работать для всехFunctor s.

Но traverse работает только для подмножества Functor s, которые также являются Applicative. Таким образом, тип traverse составляет более конкретно, чем разрешено для Lens es.