减少Haskell中的Monads

Question

假设我的类型定义为:

data Node = forall a b. Node (SimpleWire a b)

它SimpleWire是一个monad,a代表输入,b代表输出.我可以对那个monad做功能组合.所以假设我有wireA类型SimpleWire A B,wireB类型SimpleWire B C,做什么wireA . wireB会给我类型SimpleWire A C.

现在我想折叠那个monad的列表([Node]这种情况下的类型).就像是:

buildGraph :: [Node] -> (SimpleWire a b)
buildGraph (Node h):t = h . (buildGraph t)

如何在Haskell的类型系统中使用此代码？

Answer 1

我们无法构建[Node]提议的类型.这是因为否则我们会得到

sw1 :: SimpleWire A B
sw2 :: SimpleWire C D
buildGraph :: [Node] -> (SimpleWire a b)
buildGraph [ sw1, sw2 ] :: SimpleWire E F

这太强大了.我们能够组成任意的,不兼容的类型(错误的),然后在最后一个随机写入(错误).

问题是我们丢失了该类型中的所有类型信息[Node].我们需要记住一些,即:

1. 第一种和最后一种导线类型是已知的(中间导线类型不是)
2. 在列表中,每个相邻节点都是可组合的

因此,我们获得了自定义GADT列表类型

data NodeList a b where
   Nil  :: NodeList a a
   Cons :: Node a b -> NodeList b c -> NodeList a c

然后

buildGraph :: NodeList a b -> SimpleWire a b
buildGraph Nil = id  
buildGraph (Cons (Node h) t) = h . buildGraph t

Answer 2

我将假设以下故事:

你可能用过这种类型

data Node = forall a b. Node (SimpleWire a b)

而不只是SimpleWire a b因为你想要一个列表SimpleWire的位置a和b不同.特别是,你真正希望作为参数的buildGraph东西是(在伪Haskell中)

buildGraph :: [SimpleWire a b, SimpleWire b c, ..., SimpleWire x y] -> SimpleWire a y

你不能用Haskell的标准同源表达第一个列表,[]并试图使用普遍量化的类型来让你摆脱那个泡菜.

如果我说的是真的,你可能正在寻找类型线程列表或"thrists".特别是,你可以Node完全取消.一个Thrist (->) a b是功能列表a -> a1,a1 -> a2..., an -> b.更一般地Thrist f a b是名单f小号f a a1,f a1 a2,..., f an b.

{-# LANGUAGE GADTs #-}
import qualified Data.Thrist as DT

-- Note that I'll be using (>>>) as a flipped form of (.), i.e. 
-- (>>>) = flip (.)
-- (>>>) is in fact an Arrow operation which is significantly more general
-- than function composition. Indeed your `SimpleWire` type is almost
-- definitely an arrow.
import Control.Arrow ((>>>))

-- A simple take on SimpleWire
type SimpleWire = (->)

-- Ugh a partial function that blows up if the thrist is empty
unsafeBuildGraph :: DT.Thrist SimpleWire a b -> SimpleWire a b
unsafeBuildGraph = DT.foldl1Thrist (>>>)

-- Making it total
buildGraph :: DT.Thrist SimpleWire a b -> Maybe (SimpleWire a b)
buildGraph DT.Nil = Nothing
buildGraph (wire `DT.Cons` rest) = Just $ DT.foldlThrist (>>>) wire rest

-- For syntactic sugar
(*::*) = DT.Cons
infixr 6 *::*

trivialExample :: DT.Thrist SimpleWire a a
trivialExample = id *::* id *::* DT.Nil

lessTrivialExample :: (Num a, Show a) => DT.Thrist SimpleWire a String
lessTrivialExample = (+ 1) *::* (* 2) *::* show *::* DT.Nil

-- result0 is "12"
result0 = (unsafeBuildGraph lessTrivialExample) 5

-- result1 is Just "12"
result1 = fmap ($ 5) (buildGraph lessTrivialExample)

附注:

虽然SimpleWire很可能是monad,但这可能不会直接帮助你.特别是当函数是monad时,你似乎关心的是概括函数组合的概念,这是箭头的含义(并且它只与monad有间接关系).在我使用过>>>并且Thrist有一个Arrow实例的事实中有一些暗示.正如我在代码的评论中提到的,SimpleWire可能是一个Arrow.