在 Haskell 中减少 Monad

Question

假设我定义了一个类型：

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

SimpleWire是一个monad，其中a代表输入，b代表输出。我可以对那个 monad 进行函数组合。所以假设我有 SimpleWire A B 类型的 wireA 和 SimpleWire B C 类型的 wireB，做 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] 类型中的所有类型信息。我们需要记住一些，即：

第一个和最后一个电线类型已知（中间的不知道）
在列表中，每个相邻节点都是可组合的

所以，我们得到一个自定义的 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 的标准同构 [] 表达第一个列表，并尝试使用通用量化类型来让你摆脱困境。

如果我说的是真的，您可能正在寻找 type-threaded lists or "thrists"。特别是，您可以完全取消 Node。 Thrist (->) a b 是函数列表 a -> a1、a1 -> a2、...、an -> b。更一般地说，Thrist f a b 是 fs 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，但您似乎关心的是泛化函数组合的概念，这就是 arrows 的用途（并且仅与 monad 有间接关系）。我使用 >>> 并且 Thrist 有一个 Arrow 实例这一事实暗示了这一点。正如我在代码注释中提到的，SimpleWire 可能是 Arrow.

在 Haskell 中减少 Monad

Reducing over Monads in Haskell

monads

haskell

monad-transformers