haskell - 用于用 `Nothing` 发送无解决方案列表信号的 Monad 变压器

Question

向哈斯凯勒同胞们问好。

这是一个更大的约束满足问题的玩具版本，我是目前正在努力。

下面的代码使用列表 monad 转换器来表示给定的正整数n作为不同小偶数的总和方法。

import Control.Monad.Trans.List
import Control.Monad

sumToN' :: Int -> ListT Maybe [Int]
sumToN' n
  | n == 0 = pure []
  | otherwise = 
      do
        x <- ListT $ Just [1..4]
        guard $ x <= n
        guard $ even x
        fmap (x:) $ sumToN' $ n - x

加载到 GHCi 后，该函数按预期工作。

λ> sumToN' 8
ListT (Just [[2,2,2,2],[2,2,4],[2,4,2],[4,2,2],[4,4]])
λ> sumToN' 7
ListT (Just [])

但是，我希望通过定义一个如果没有解决方案，该函数将返回 ListT Nothing成立。这不是我得到的。我得到的结果很可能是如何为 ListT 定义 mzero 的结果。

λ> mzero :: ListT Maybe [Int]
ListT (Just [])

我的问题是:是否可以使用 monad 转换器来组合列表和也许，这样Nothing将表明在代码。(我不是在寻找黑客。我想知道 monad 是否变压器会以某种方式直接支持这一点。)

作为背景信息，以下代码不使用 monad变压器完全并达到与上面相同的结果通过[]表示无解。

sumToN :: Int -> [[Int]]
sumToN 0 = [[]]
sumToN n = do
  x <- [1..4]
  guard $ x <= n
  guard $ even x
  map (x:) $ sumToN $ n - x

这给了我们与列表转换器基本相同的结果。

λ> sumToN 8
[[2,2,2,2],[2,2,4],[2,4,2],[4,2,2],[4,4]]
λ> sumToN 7
[]

Answer 1

虽然我认为简单地删除也许是惯用的解决方案，但以下是您所问问题的答案。由于我们知道 monad 转换器堆栈的确切性质，因此我们可以使用模式匹配来反射(reflection)其值。

testList :: ListT Maybe a -> ListT Maybe a
testList (ListT (Just [])) = ListT Nothing
testList x = x

如果你想要更多地与类型系统对话，你可以用 NonEmpty 构造一个 monad 实例。 (请记住，这不会比 ListT 更好地表现良好的 monad 转换器，但它会做你想要的事情)。我们可以将其称为 NonEmptyT。

newtype NonEmptyT m a = NonEmptyT { unNonEmptyT :: m (NonEmpty a) }

-- Instance implementations omitted for brevity

instance Functor m => Functor (NonEmptyT m) where
    ...

instance Applicative m => Applicative (NonEmptyT m) where
    ...

instance Monad m => Monad (NonEmptyT m) where
    ...

instance MonadTrans NonEmptyT where
    ...

现在我们可以写了

testList' :: [a] -> NonEmptyT Maybe a
testList' [] = NonEmptyT Nothing
testList' (x:xs) = NonEmptyT $ Just (x :| xs)

这需要一个普通列表并将其转换为NonEmptyT Maybe。这与您之前的方法的不同之处在于，您不喜欢的值 (ListT (Just [])) 在我们的新类型中甚至没有意义。您可以使用 NonEmptyT Nothing，也可以使用 NonEmptyT (Just someNonemptyList)，但表达式 NonEmptyT (Just []) 甚至不会进行类型检查。

这并不完全是您正在寻找的行为，变压器实际上与它下面的层进行交互并理解它下面的层，但我认为这是朝着正确方向迈出的一步，因为它完全禁止程序员构建您想要的值不想存在。

Full working example .

<小时/>

(脚注:不幸的是，GHC 不想让我在这个新类型上使用 GeneralizedNewtypeDeriving 或 DeriveFunctor，所以你实际上必须通过以下方式编写实例手。如果有人知道为什么这些扩展在这种情况下失败，我很想知道原因。)