在Haskell中实现List#flatten

Question

Scala提供了一个List#flatten方法，用于从List[Option[A]]到List[A]。

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，则放弃它。否则，通过模式分配x，将值与Just 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中提取f构造函数中的值，就可以完全避免g。

顺便说一句，f已经存在了，因为maybeToList和flatten都在Data.Maybe中被称为catMaybes。

Answer 3

我们可以很容易地编写一个简单的递归函数，它会遍历一个列表，并拒绝所有可能是单变量的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函数现在是您所称的“完全”，尽管更准确地说，它具有详尽的模式。

您可以找到关于函数语法这里的更多信息。