在依赖类型的函数式编程语言中扁平化列表更容易吗？
Is flattening a list easier in dependently typed functional programming languages?
在 haskell 中寻找一个可以压平任意深度嵌套列表的函数，即递归应用 concat 并在最后一次迭代（非嵌套列表）处停止的函数，我请注意，这将需要一个更灵活的类型系统，因为随着列表深度的变化，输入类型也会发生变化。事实上，有几个 Whosebug 问题 - 例如 this 一个 - 其中的响应声明“不存在将 'look' 在不同深度的不同嵌套列表中的函数”。
编辑：一些答案在 haskell 中提供了解决方法，无论是针对自定义数据类型还是在 TypeFamilies 或 MultiParamTypeClasses 的帮助下（如下面 Noughtmare 的回答或答案通过 'Landei' 在 post above or the answer by 'John L' in this post 中）。
然而，那些家庭和 类 似乎也被引入，因为缺少 / 来替代 haskell 中的依赖类型（例如，haskell wiki 状态 “类型家庭[...] 很像依赖类型.
我现在的问题是 haskell 是否确实 最初 不是为了定义此类函数（例如展平不同深度的列表），而且， ，一旦转向一种实现 dependent types 的语言，这些问题是否会消失？ （例如 Idris、Agda、Coq，...）我没有使用这些语言的经验，这就是我问的原因。
例如，在 Idris 网站上，据说“类型可以作为参数传递给函数”，因此，我认为，在列表扁平化的情况下，可以简单地传递列为参数并以直接的方式实现所需的功能。这可能吗？
后续问题也将是：在 haskell 中解决此问题的那些家族和 类 是否在 haskell 中提供了依赖类型理论的完整实现，或者如果不，重要的区别是什么？
您可以在 Haskell 中创建一个不需要指定输出类型的函数：
{-# LANGUAGE TypeFamilies, FlexibleInstances, FlexibleContexts #-}
type family FlatT a where
FlatT [[a]] = FlatT [a]
FlatT a = a
class Flat a where
flat :: a -> FlatT a
instance Flat [a] => Flat [[a]] where
flat xs = flat $ concat xs
instance {-# OVERLAPPABLE #-} FlatT a ~ a => Flat a where
flat x = x
main = print $ flat [["Hello"," "],["World", "!"]]
仍然存在的一个问题是您的列表中可能包含一个多态类型，它本身可能是一个列表。例如你可以写一个整数列表：
main = print $ flat [[1,2],[3,4,5]]
这会给出很多关于不明确变量的错误。一个简单的修复方法是向其中一个整数添加类型签名：[[1,2],[3,4,5 :: Int]]。这将修复所有错误。从某种意义上说，这个错误对我来说是不可避免的，因为你可以这样写一个实例：
instance Num [Int] where
fromInteger n = replicate (fromInteger n) (fromInteger n)
然后你可以这样使用它：
main = print $ [[1,2],[3,4,5 :: [Int]]]
哪个 return:
[1,2,2,3,3,3,4,4,4,4,5,5,5,5,5]
如您所见，这会额外展开一层。因此，展开的层数取决于您在签名中提供的类型。对我来说，这听起来像是无法避免类型签名，即使是在更强大的语言中也是如此。
泛型是完成此类任务的好工具。如果你的类型是 Data 的实例，你可以写
import Data.Generics
import Control.Monad
gFind :: (MonadPlus m, Data a, Typeable b) => a -> m b
gFind = msum . map return . listify (const True)
所以，
λ> gFind [[1,2],[3,4,5]] :: [Integer]
[1,2,3,4,5]
λ> gFind ((1,"b"),(2,"d","e")) :: [Integer]
[1,2]
在 Haskell 中模仿“任意深度嵌套列表”的常用方法是使用 free monads.
语言库中包含免费的 monad，作为包 Control.Monad.Free。
所以我们可以尝试将“多级列表”实现为MLL类型转换器：
import Control.Monad
import Control.Monad.Free
-- Multi-Level List:
type MLL = Free []
mllJoin :: [MLL a] -> MLL a
mllJoin = Free
mllWrap :: a -> MLL a
mllWrap = return
现在的问题是：我们如何扁平化这样一个对象？
好吧，一个可能的说法是，如果 Free 类型构造函数的仿函数参数 ft 是 Foldable class 的实例，那么 Free ft 也是.
因此，[]是可折叠的，我们的MLL型变压器也是可折叠的。
foldr的类型，例如：
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
可以这样特化：
foldr :: (a -> acct -> acct) -> acct -> MLL a -> acct
累加器类型为 acct。
这给出了选择 acct 作为 [a] 并将 cons 作为 foldr 的函数参数的想法。像这样：
mllFlatten :: MLL a -> MLL a
mllFlatten xs = let fl1 = foldr (:) [] xs
in mllJoin (fmap mllWrap fl1)
测试程序：
main :: IO ()
main = do
-- try build a small multilevel structure as zs:
let xs = (mllJoin [ mllWrap 41, mllWrap 42 ]) :: (MLL Integer)
ys = mllJoin [ xs, mllWrap 43 ]
zs = mllJoin [ mllWrap 40, ys, mllWrap 44 ]
putStrLn $ "zs = " ++ (show zs)
-- display structure of zs:
let zsImage = filter (\ch -> not (elem ch "Pure Free")) (show zs)
putStrLn $ "zsImage = " ++ zsImage
-- flattening zs:
let fzs = mllFlatten zs
putStrLn $ "Flattened zs = " ++ (show fzs)
-- display structure of flattened zs:
let fzsImage = filter (\ch -> not (elem ch "Pure Free")) (show fzs)
putStrLn $ "fzsImage = " ++ fzsImage
测试程序输出：
zs = Free [Pure 40,Free [Free [Pure 41,Pure 42],Pure 43],Pure 44]
zsImage = [40,[[41,42],43],44]
Flattened zs = Free [Pure 40,Pure 41,Pure 42,Pure 43,Pure 44]
fzsImage = [40,41,42,43,44]
因此，折叠结构似乎确实使它变平了。
既然你想看看如何在 Coq 中完成，我在这里提出一个简单的解决方案。
From Coq Require Import Utf8 List.
Import ListNotations.
Fixpoint flatten {A} (l : list (list A)) : list A :=
match l with
| x :: l => x ++ flatten l
| [] => []
end.
(* Nested list type *)
Fixpoint nlist (n : nat) (A : Type) : Type :=
match n with
| 0 => A
| S n => list (nlist n A)
end.
Fixpoint nflatten {n A} (l : nlist n A) : list A :=
match n as m
return nlist m A → list A
with
| 0 => λ x, [ x ]
| S n => λ l, flatten (map nflatten l)
end l.
Eval compute in
nflatten (n := 2) [
[ 1 ; 2 ; 3 ] ;
[ 4 ; 5 ] ;
[] ;
[ 6 ]
].
(* = [1; 2; 3; 4; 5; 6]
: list nat *)
Eval compute in
nflatten (n := 3) [
[ [1] ; [2 ; 3] ] ;
[ [4 ; 5] ] ;
[] ;
[ [6] ]
].
(* = [1; 2; 3; 4; 5; 6]
: list nat *)
我首先以一种天真的方式重新定义了flatten，然后我定义了一种嵌套列表nlist，它带有一个对应于深度的自然数。
我假设您希望所有列表的深度恒定，否则解决方案会稍微复杂一些。
那么nflatten就简单的对自然数做个案例分析来做展平
在 haskell 中寻找一个可以压平任意深度嵌套列表的函数，即递归应用 concat 并在最后一次迭代（非嵌套列表）处停止的函数，我请注意，这将需要一个更灵活的类型系统，因为随着列表深度的变化，输入类型也会发生变化。事实上，有几个 Whosebug 问题 - 例如 this 一个 - 其中的响应声明“不存在将 'look' 在不同深度的不同嵌套列表中的函数”。
编辑：一些答案在 haskell 中提供了解决方法，无论是针对自定义数据类型还是在 TypeFamilies 或 MultiParamTypeClasses 的帮助下（如下面 Noughtmare 的回答或答案通过 'Landei' 在 post above or the answer by 'John L' in this post 中）。
然而，那些家庭和 类 似乎也被引入，因为缺少 / 来替代 haskell 中的依赖类型（例如，haskell wiki 状态 “类型家庭[...] 很像依赖类型.
我现在的问题是 haskell 是否确实 最初 不是为了定义此类函数（例如展平不同深度的列表），而且， ，一旦转向一种实现 dependent types 的语言，这些问题是否会消失？ （例如 Idris、Agda、Coq，...）我没有使用这些语言的经验，这就是我问的原因。
例如，在 Idris 网站上，据说“类型可以作为参数传递给函数”，因此，我认为，在列表扁平化的情况下，可以简单地传递列为参数并以直接的方式实现所需的功能。这可能吗？
后续问题也将是：在 haskell 中解决此问题的那些家族和 类 是否在 haskell 中提供了依赖类型理论的完整实现，或者如果不，重要的区别是什么？
您可以在 Haskell 中创建一个不需要指定输出类型的函数：
{-# LANGUAGE TypeFamilies, FlexibleInstances, FlexibleContexts #-}
type family FlatT a where
FlatT [[a]] = FlatT [a]
FlatT a = a
class Flat a where
flat :: a -> FlatT a
instance Flat [a] => Flat [[a]] where
flat xs = flat $ concat xs
instance {-# OVERLAPPABLE #-} FlatT a ~ a => Flat a where
flat x = x
main = print $ flat [["Hello"," "],["World", "!"]]
仍然存在的一个问题是您的列表中可能包含一个多态类型，它本身可能是一个列表。例如你可以写一个整数列表：
main = print $ flat [[1,2],[3,4,5]]
这会给出很多关于不明确变量的错误。一个简单的修复方法是向其中一个整数添加类型签名：[[1,2],[3,4,5 :: Int]]。这将修复所有错误。从某种意义上说，这个错误对我来说是不可避免的，因为你可以这样写一个实例：
instance Num [Int] where
fromInteger n = replicate (fromInteger n) (fromInteger n)
然后你可以这样使用它：
main = print $ [[1,2],[3,4,5 :: [Int]]]
哪个 return:
[1,2,2,3,3,3,4,4,4,4,5,5,5,5,5]
如您所见，这会额外展开一层。因此，展开的层数取决于您在签名中提供的类型。对我来说，这听起来像是无法避免类型签名，即使是在更强大的语言中也是如此。
泛型是完成此类任务的好工具。如果你的类型是 Data 的实例，你可以写
import Data.Generics
import Control.Monad
gFind :: (MonadPlus m, Data a, Typeable b) => a -> m b
gFind = msum . map return . listify (const True)
所以，
λ> gFind [[1,2],[3,4,5]] :: [Integer]
[1,2,3,4,5]
λ> gFind ((1,"b"),(2,"d","e")) :: [Integer]
[1,2]
在 Haskell 中模仿“任意深度嵌套列表”的常用方法是使用 free monads.
语言库中包含免费的 monad，作为包 Control.Monad.Free。
所以我们可以尝试将“多级列表”实现为MLL类型转换器：
import Control.Monad
import Control.Monad.Free
-- Multi-Level List:
type MLL = Free []
mllJoin :: [MLL a] -> MLL a
mllJoin = Free
mllWrap :: a -> MLL a
mllWrap = return
现在的问题是：我们如何扁平化这样一个对象？
好吧，一个可能的说法是，如果 Free 类型构造函数的仿函数参数 ft 是 Foldable class 的实例，那么 Free ft 也是.
因此，[]是可折叠的，我们的MLL型变压器也是可折叠的。
foldr的类型，例如：
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
可以这样特化：
foldr :: (a -> acct -> acct) -> acct -> MLL a -> acct
累加器类型为 acct。
这给出了选择 acct 作为 [a] 并将 cons 作为 foldr 的函数参数的想法。像这样：
mllFlatten :: MLL a -> MLL a
mllFlatten xs = let fl1 = foldr (:) [] xs
in mllJoin (fmap mllWrap fl1)
测试程序：
main :: IO ()
main = do
-- try build a small multilevel structure as zs:
let xs = (mllJoin [ mllWrap 41, mllWrap 42 ]) :: (MLL Integer)
ys = mllJoin [ xs, mllWrap 43 ]
zs = mllJoin [ mllWrap 40, ys, mllWrap 44 ]
putStrLn $ "zs = " ++ (show zs)
-- display structure of zs:
let zsImage = filter (\ch -> not (elem ch "Pure Free")) (show zs)
putStrLn $ "zsImage = " ++ zsImage
-- flattening zs:
let fzs = mllFlatten zs
putStrLn $ "Flattened zs = " ++ (show fzs)
-- display structure of flattened zs:
let fzsImage = filter (\ch -> not (elem ch "Pure Free")) (show fzs)
putStrLn $ "fzsImage = " ++ fzsImage
测试程序输出：
zs = Free [Pure 40,Free [Free [Pure 41,Pure 42],Pure 43],Pure 44]
zsImage = [40,[[41,42],43],44]
Flattened zs = Free [Pure 40,Pure 41,Pure 42,Pure 43,Pure 44]
fzsImage = [40,41,42,43,44]
因此，折叠结构似乎确实使它变平了。
既然你想看看如何在 Coq 中完成，我在这里提出一个简单的解决方案。
From Coq Require Import Utf8 List.
Import ListNotations.
Fixpoint flatten {A} (l : list (list A)) : list A :=
match l with
| x :: l => x ++ flatten l
| [] => []
end.
(* Nested list type *)
Fixpoint nlist (n : nat) (A : Type) : Type :=
match n with
| 0 => A
| S n => list (nlist n A)
end.
Fixpoint nflatten {n A} (l : nlist n A) : list A :=
match n as m
return nlist m A → list A
with
| 0 => λ x, [ x ]
| S n => λ l, flatten (map nflatten l)
end l.
Eval compute in
nflatten (n := 2) [
[ 1 ; 2 ; 3 ] ;
[ 4 ; 5 ] ;
[] ;
[ 6 ]
].
(* = [1; 2; 3; 4; 5; 6]
: list nat *)
Eval compute in
nflatten (n := 3) [
[ [1] ; [2 ; 3] ] ;
[ [4 ; 5] ] ;
[] ;
[ [6] ]
].
(* = [1; 2; 3; 4; 5; 6]
: list nat *)
我首先以一种天真的方式重新定义了flatten，然后我定义了一种嵌套列表nlist，它带有一个对应于深度的自然数。
我假设您希望所有列表的深度恒定，否则解决方案会稍微复杂一些。
那么nflatten就简单的对自然数做个案例分析来做展平