如何在Haskell中实现多维列表扁平化并修复空列表适配问题

问题分析 #

你当前实现的flatten_l函数类型签名为[[a]] -> [a]，天生仅支持二维列表的扁平化操作，和Prelude自带的concat函数功能完全一致。你所说的输入[[]]运行“异常”实际是符合二维扁平化语义的正常结果：flatten_l [[]]会返回[]，如果该结果不符合你的预期，说明你需要支持任意深度嵌套列表的通用扁平化能力。

任意维度嵌套列表扁平化实现 #

Haskell是静态强类型语言，要实现任意深度的列表扁平化，需要借助GHC的类型扩展和类型类做动态分派，实现代码如下：

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE OverlappingInstances #-}
{-# LANGUAGE UndecidableInstances #-}

class Flattenable a where
  flatten :: a -> [b]

instance {-# OVERLAPS #-} Flattenable [b] where
  flatten [] = []
  flatten (x:xs) = flatten x ++ flatten xs

instance {-# INCOHERENT #-} Flattenable b where
  flatten x = [x]

效果验证 #

你可以用以下测试用例验证功能：

• 二维空嵌套输入：flatten [[]] 输出 []
• 三维嵌套输入：flatten [[1,2], [[3], [4,5,[]]], 6] 输出 [1,2,3,4,5,6]
• 你提供的原测试用例：flatten [[1,2,3], [4,5], [6], [], [7,8,9], []] 输出 [1,2,3,4,5,6,7,8,9]

内容的提问来源于stack exchange，提问作者Nitin bora