如何对迭代中类型发生变化但函数形式相同的函数进行"迭代"

Question

我刚刚开始学习Haskell,我遇到了以下问题.我试着"迭代"这个功能\x->[x].我期望得到的结果[[8]]通过

foldr1 (.) (replicate 2 (\x->[x])) $ (8 :: Int)

这不起作用,并给出以下错误消息:

发生检查:无法构造无限类型: a ~ [a]

预期类型: [a -> a]

实际类型: [a -> [a]]

我能理解为什么它不起作用.这是因为它foldr1具有类型签名foldr1 :: Foldable t => (a -> a -> a) -> a -> t a -> a,并且不a -> a -> a作为其第一个参数的类型签名a -> a -> b

这也不是,出于同样的原因:

((!! 2) $ iterate (\x->[x]) .) id) (8 :: Int)

但是,这有效:

(\x->[x]) $ (\x->[x]) $ (8 :: Int)

我明白第一个(\x->[x])和第二个是不同类型的(即[Int]->[[Int]]和Int->[Int]),虽然形式上它们看起来是一样的.

现在说我需要将2改为大数,比如说100.

我的问题是,有没有办法建立这样的清单？我是否必须采用模板Haskell等元编程技术？如果我不得不求助于元编程,我该怎么办呢？

作为一个副节点,我也尝试构造这样一个列表的字符串表示形式read.虽然字符串更容易构造,但我不知道如何使用read这样的字符串.例如,

read "[[[[[8]]]]]" :: ??

??当嵌套层的数量不是先验已知时,我不知道如何构造零件.我能想到的唯一方法就是采用元编程.

上面的问题似乎不够有趣,我有一个"现实生活"的案例.考虑以下功能:

natSucc x = [Left x,Right [x]]

这是自然数succ的形式定义中使用的函数.再说一遍,我不能简单地foldr1-replicate或者!!-iterate它.

任何帮助将不胜感激.关于代码样式的建议也是受欢迎的.

编辑:在查看到目前为止给出的3个答案之后(再次,非常感谢您的时间和努力)我意识到这是一个更普遍的问题,不仅限于列表.对于每种有效类型的仿函数,可以编写类似的问题(如果我想得到的话Just Just Just 8,虽然这本身可能没有多大意义？).

Answer 1

你肯定同意2 :: Int并4 :: Int拥有相同的类型.因为Haskell不依赖于^†,这意味着foldr1 (.) (replicate 2 (\x->[x])) (8 :: Int)并且foldr1 (.) (replicate 4 (\x->[x])) (8 :: Int)必须具有相同的类型,这与前者应该给出的想法[[8]] :: [[Int]]和后者的想法相矛盾[[[[8]]]] :: [[[[Int]]]].特别是,应该可以将这两个表达式放在一个列表中(Haskell列表需要为其所有元素使用相同的类型).但这只是行不通.

关键是你并不真正想要一个Haskell列表类型:你希望能够在一个结构中拥有不同深度的分支.好吧,你可以拥有它,它不需要任何聪明的类型系统黑客 - 我们只需要清楚这不是一个列表,而是一棵树.像这样的东西:

data Tree a = Leaf a | Rose [Tree a]

那你可以做

Prelude> foldr1 (.) (replicate 2 (\x->Rose [x])) $ Leaf (8 :: Int)
Rose [Rose [Leaf 8]]
Prelude> foldr1 (.) (replicate 4 (\x->Rose [x])) $ Leaf (8 :: Int)
Rose [Rose [Rose [Rose [Leaf 8]]]]

^† _{实际上,现代GHC Haskell有很多依赖类型的功能(参见DaniDiaz的回答),但这些仍然与价值级语言明显分开.}

Answer 2

我想提出一个非常简单的替代方案,它不需要任何扩展或欺骗:不要使用不同的类型.

这是一种类型,可以保存包含任意数量嵌套的列表,只要你说前面有多少:

data NestList a = Zero a | Succ (NestList [a]) deriving Show
instance Functor NestList where
    fmap f (Zero a) = Zero (f a)
    fmap f (Succ as) = Succ (fmap (map f) as)

这种类型的值是一个教堂数字,表示有多少层嵌套,后面是一个嵌套多层的值; 例如,

Succ (Succ (Zero [['a']])) :: NestList Char

编写\x -> [x]迭代现在很简单; 因为我们想要一层嵌套,所以我们添加一层Succ.

> iterate (\x -> Succ (fmap (:[]) x)) (Zero 8) !! 5
Succ (Succ (Succ (Succ (Succ (Zero [[[[[8]]]]])))))

您可以类似地修改关于如何实现自然数的提议,以使用简单的递归类型.但标准方式更清晰:只需采取上述内容NestList并删除所有参数即可.

data Nat = Zero | Succ Nat