如何在 Haskell 中创建一定深度的列表

Question

他最近开始学习 Haskell。我有一个任务：用两个计算参数——数字 N 和原子 A 对函数 bubl N A 进行编程。该函数构建一个深度为 N 的列表；在最深层次上，列表的一个元素是 A，而在任何其他层次上，列表由一个元素组成。例如：bubl 3 5 => [[[5]]].

这是我解决这个问题的失败尝试：

bubl :: Integer -> a -> [a] -> [a]
bubl n b list
  | n == 0 = take 1 ([head list] : list)
  | n /= 0 = bubl (n - 1) b (take 1 [head list] : ---list)

我只是这方面的初学者，所以我需要你的帮助）

Answer 1

有一些高级方法可以解决此问题（见下文），但 Haskell 类型系统（设计）将阻止您为此任务编写直接的解决方案。

问题是 Haskell 函数通常无法根据输入参数更改其结果的类型，因此您不能在 Haskell 中编写函数定义，看起来像这个：

weird 1 = False            -- type is Bool
weird 2 = "Hello world!"   -- type is String
weird 3 = 42               -- type is Int, say

您尝试编写的 bubl 函数存在类似的问题，因为给定的列表类型具有固定的深度，如果深度取决于第一个参数，则结果的类型将不同取决于那个论点：

bubl 1 5 = [5]     -- type is [Int]
bubl 2 5 = [[5]]   -- type is [[Int]]
bubl 3 5 = [[[5]]] -- type is [[[Int]]]

最简单的解决方案（尽管对于初学者来说仍然有点高级）是定义一个新的 user-defined 类型，它可以表示不同深度的“列表”，但只使用一种类型。在实际程序中，这种类型的形式取决于使用 bubl 的上下文。在像这样的人工编程任务中，我们必须猜测。如果您希望能够表示可以任意嵌套到不同深度的整数“列表”，例如假设的“列表”：

[1,[1,2,3],[[4,[5],[[[[6]]]]]]]   -- note: not a valid Haskell list!

那么您可能会定义一个 Haskell 类型，例如：

data NestedList = Atom Int | Nest [NestedList]

或更一般地，对于具有潜在 non-integer 个原子的嵌套列表：

data NestedList a = Atom a | Nest [NestedList a]

上面的假设列表在使用这个新类型定义时看起来像这样：

ex1 = Nest [ Atom 1
           , Nest [Atom 1, Atom 2, Atom 3]
           , Nest [Nest [ Atom 4
                        , Nest [Atom 5]
                        , Nest [Nest [Nest [Nest [Atom 6]]]]
                        ]
                  ]
           ]

并且您可以定义一个使用此表示的 bubl 版本：

bubl :: Integer -> a -> NestedList a
bubl 0 b = Atom b
bubl n b = Nest [bubl (n-1) b]

如果您编写一个函数将 NestedList 转换为漂亮的字符串表示形式：

import Data.List (intercalate)

showNest :: (Show a) => NestedList a -> String
showNest (Atom a) = show a
showNest (Nest xs) = "[" ++ intercalate "," (map showNest xs) ++ "]"

您可以获得您希望的那种输出：

λ> putStrLn $ showNest (bubl 3 5)
[[[5]]]

还有其他解决方案与普通 Haskell 列表保持一致，但它们要高级得多。一个聪明的解决方案使用类型类让调用者确定列表的深度，从而无需将深度作为参数传递：

class Bubl a where
  bubl :: Int -> a
instance Bubl a => Bubl [a] where
  bubl x = [bubl x]
instance Bubl Int where
  bubl = id

main = do
  print (bubl 3 :: Int)
  print (bubl 3 :: [Int])
  print (bubl 3 :: [[[Int]]])

有了很多复杂的扩展，您可以调整此解决方案以采用 type-level 深度参数，这通过稍微修改语法（调用中的 @-sign）解决了原始任务。我包含这个例子只是为了表明它 技术上 可能具有许多高级 Haskell 功能。复杂性说明您真的不应该在“正常”Haskell 代码中执行此操作。

{-# LANGUAGE AllowAmbiguousTypes #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE UndecidableInstances #-}

import GHC.TypeLits

class Bubl a where
  bubl :: Int -> a
instance Bubl a => Bubl [a] where
  bubl x = [bubl x]
instance Bubl Int where
  bubl = id

type family Nested n where
  Nested 0 = Int
  Nested n = [Nested (n-1)]

bubl' :: forall n. (Bubl (Nested n)) => Int -> Nested n
bubl' = bubl

main = do
  print $ bubl' @0 5   -- prints "5"
  print $ bubl' @3 5   -- prints "[[[5]]]"

如何在 Haskell 中创建一定深度的列表

How to create a list of a certain depth in Haskell

haskell