在 Haskell 中实现列表#扁平化

Question

Scala提供了一种从List[Option[A]]到List[A]的List#flatten方法。

scala> val list = List(Some(10), None)
list: List[Option[Int]] = List(Some(10), None)
scala> list.flatten
res11: List[Int] = List(10)

我试图在 Haskell 中实现它：

flatten :: [Maybe a] -> [a]
flatten xs = map g $ xs >>= f
f :: Maybe a -> [Maybe a]
f x = case x of Just _  -> [x]
                Nothing -> []
-- partial function!
g :: Maybe a -> a
g (Just x) = x

但是，我不喜欢g是一个部分的，即非总的函数。

有没有一种完整的方法来编写这样的flatten函数？

Answer 1

您的flatten与catMaybes（链接）相同，其定义如下：

catMaybes :: [Maybe a] -> [a]
catMaybes ls = [x | Just x <- ls]

列表推导中的特殊语法Just x <- ls意味着从ls中提取元素，如果它不是Just则丢弃它。否则，通过与Just x匹配值的模式分配x。

Answer 2

对你拥有的代码稍作修改就可以了：

flatten :: [Maybe a] -> [a]
flatten xs = xs >>= f
f :: Maybe a -> [a]
f x = case x of Just j  -> [j]
                Nothing -> []

如果我们在 f 中提取 Just 构造函数内部的值，我们完全避免g。

顺便说一下，f已经以maybeToList的形式存在，flatten被称为catMaybes，两者都在Data.Maybe中。

Answer 3

人们可以很容易地编写一个简单的递归函数，它通过一个列表并拒绝来自 May monad 的所有Nothing。以下是我作为递归序列的操作方法：

flatten :: [Maybe a] -> [a]
flatten [] = []
flatten (Nothing : xs) =     flatten xs
flatten (Just x  : xs) = x : flatten xs

但是，将其写成折叠可能更清楚：

flatten :: [Maybe a] -> [a]
flatten = foldr go []
    where go  Nothing xs =     xs
          go (Just x) xs = x : xs

或者，由于@user2407038，我们可以使用一个非常优雅的解决方案，我建议在 GHCi 中使用它来解决各个函数的工作：

flatten :: [Maybe a] -> [a]
flatten = (=<<) (maybe [] (:[])

而且速度更快，折叠兄弟：

flatten :: [Maybe a] -> [a]
flatten = foldr (maybe id (:))

您的解决方案已经成功了一半。我的建议是重写你的函数f使用模式匹配（如我的临时go函数），并将其包含在where语句中，以将相关函数保存在一个地方。你必须记住scala和Haskell中函数语法的差异。

你

遇到的大问题是你不知道我提到的差异。您的g函数可以使用具有多个模式的模式匹配：

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

你去吧：你的g函数现在是你所说的"完整"，尽管更准确地说，它应该说具有详尽的模式。

您可以在此处找到有关函数语法的更多信息。