Почему неполиморфный тип не может реализовать Foldable в Haskell? - PullRequest
Новая
       65

Почему неполиморфный тип не может реализовать Foldable в Haskell?

4 голосов
/ 16 апреля 2019

Скажем, у меня есть несколько упрощенных типов Expr в стиле lisp: 

data Expr = String String | Cons Expr Expr
  deriving (Show)

Я могу создавать списки в виде Cons-клеток Cons-клеток: 

Cons (String "hello") (Cons (String "World") (String "!"))

Из этогоЯ хотел бы реализовать Foldable для Expr, чтобы сложить эти списки минусов - но это невозможно, поскольку Foldable требует тип вида * -> * (т.е. полиморфный с ровно одним параметром типа), где мой Expr имеет вид *.

Почему это так?Мне кажется, что сворачивание поверх неполиморфных типов, как в этом случае, было бы совершенно разумным, но, очевидно, я что-то упустил.

1 Ответ

5 голосов
/ 17 апреля 2019

Мне кажется, что сворачивание поверх неполиморфных типов, как в этом случае, было бы совершенно разумным, но, очевидно, я что-то упускаю.

Это действительно разумно. Один из способов складывания мономорфного контейнера - использование MonoFoldable. Другой использует a Fold от объектив или из какой-либо другой библиотеки оптики: 

import Control.Lens

data Expr = String String | Cons Expr Expr
  deriving (Show)

-- A Traversal can also be used as a Fold.
-- strings :: Applicative f => (String -> f String) -> (Expr -> f Expr) 
strings :: Traversal' Expr String
strings f (String s) = String <$> f s
strings f (Cons l r) = Cons <$> strings f l <*> strings f r 

GHCi> hello = Cons (String "hello") (Cons (String "World") (String "!"))
GHCi> toListOf strings hello
["hello","World","!"]
GHCi> import Data.Monoid
GHCi> foldMapOf strings (Sum . length) hello
Sum {getSum = 11}

Что касается того, почему Foldable экземпляры имеют вид * -> *, а не *, я бы объяснил это сочетанием простоты и исторических причин. Исторически говоря, Foldable является ответвлением Traversable, и стоит отметить, что, хотя мономорфные обходы могут быть полезны, их ограничения гораздо более поразительны, чем ограничения, которые влияют на мономорфные складки (например, вы не можете восстановить fmap из них, но просто мономорфный omap). Наконец, вопросы и ответы, предложенные Джозефом Сиблеем, Есть ли что-то, что мы теряем с MonoFoldable? , включает в себя несколько интересных обсуждений потенциальных причин не прямой замены Foldable на MonoFoldable.

...