使用 Haskell 将随机嵌套列表展平为非嵌套列表

Question

我有一个具有不同嵌套级别的假想列表，或者忽略丑陋的类型 API 响应即：

a ::(Num a, Num [a], Num [[a]]) => [[a]]
a = [1, 2, [3, 4]]

b :: (Num a, Num [a], Num [[a]], Num [[[a]]]) => [[[[a]]]]
b = [[1,2,[3]],4]

我尝试创建的函数应该执行以下操作：

myFunc a == [1,2,3,4]
myFunc b == [1,2,3,4]

我最初的想法是我必须将列表解析为 AST（抽象语法树）--> 使用递归将所有分支和叶子展平为一个分支 --> 解析结果返回到列表中。

我不确定如何将列表解析为 AST？或者有更好的解决方案吗？

edit——我想我太直白了，因为表示 [1, 2, [3, 4]] 实际上是问题的一部分，所以实际上为了让事情更好地工作，它们需要被表示为 ADT/AST。因此，如果这是 API 响应或读取文件，我将如何将该数据解析为 AST/ADT?

Answer 1

任意嵌套的列表不会进行类型检查。列表的每个元素必须具有相同的类型，但具有不同嵌套级别的列表具有不同的类型。解决这个问题的技巧是将列表包装成隐藏嵌套级别数的新数据类型。但这只是一棵树。

data Tree a = Root a | Branches [Tree a]

那么就可以实现flatten作为树的遍历

flatten :: Tree a -> [a]
flatten (Root a)          = [a]
flatten (Branches (t:ts)) = flatten t ++ (concat (fmap flatten ts))

请参阅容器包中的 Data.Tree 以获取即用型版本。

对于解析，我建议使用aeson。 Data.Aeson.Types 定义实例 FromJSON v => FromJSON (Tree v)，所以你应该能够在 json 字符串上使用 decode 并告诉它你想要一个 Tree Int.

decode rawJson :: Maybe (Tree Int)

Answer 2

不清楚您实际想要实现的目标，但有一个语法 hack 实际上允许您在 Haskell 中编写不同的嵌套列表语法并具有它自动变平：

{-# LANGUAGE TypeFamilies #-}

import GHC.Exts (IsList(..))

newtype AutoflatList a = AutoflatList {getFlatList :: [a]}
   deriving (Show)

instance IsList (AutoflatList a) where
  type Item (AutoflatList a) = AutoflatList a
  fromList segs = AutoflatList $ getFlatList =<< segs
  toList = pure

instance Num a => Num (AutoflatList a) where
  fromInteger = AutoflatList . pure . fromInteger

*Main> :set -XOverloadedLists
*Main> [1, 2, [3, 4]] :: AutoflatList Int
AutoflatList {getFlatList = [1,2,3,4]}
*Main> [[1,2,[3]],4] :: AutoflatList Int
AutoflatList {getFlatList = [1,2,3,4]}

除非出于娱乐目的，否则不推荐使用此解决方案。

Answer 3

这已经由 GHC 为您完成。展平就是折叠。

> :set -XDeriveFoldable

> data NList a = A a | N [NList a] deriving (Show, Functor, Foldable)
data NList a = A a | N [NList a]

> foldMap pure (N[ A 1, N[ A 2], A 3]) :: [Int]
[1,2,3]

> foldMap pure (N[ N[ N[ N[ A 1]]], N[ A 2], A 3]) :: [Int]
[1,2,3]

使用 Haskell 将随机嵌套列表展平为非嵌套列表

Flatten randomly nested list into a non nested list using Haskell

parsing

haskell

abstract-syntax-tree