如何在Haskell中創建一定深度的串列

他最近開始學習 Haskell。我有一個任務：使用兩個計算引數對函式 bubl NA 進行編程 - 數字 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)

我只是這種方式的初學者，所以我需要你的幫助）

uj5u.com熱心網友回復：

有一些高級方法可以解決這個問題（見下文），但 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]]]

最簡單的解決方案（盡管對于初學者來說仍然有些先進）是定義一個新的、用戶定義的型別，它可以表示不同深度的“串列”，但只使用一種型別。在實際程式中，這種型別的形式將取決于使用的背景關系bubl。在這樣的人工編程任務中，我們必須猜測。如果您希望能夠表示可以任意嵌套到不同深度的整數“串列”，例如假設的“串列”：

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

那么您可能會定義一個 Haskell 型別，例如：

data NestedList = Atom Int | Nest [NestedList]

或更一般地，對于具有潛在非整數原子的嵌套串列：

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]

If you write a function to convert a NestedList to a nice string representation:

import Data.List (intercalate)

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

you can get the sort of output you're hoping for:

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

There are additional solutions that stick with normal Haskell lists, but they are much more advanced. One clever solution uses type classes to let the caller determine the depth of the list, eliminating the need to pass the depth as an argument:

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]]])

With a lot of complicated extensions you can adapt this solution to take a type-level depth argument, which solves the original task with slightly modified syntax (an @-sign in the call). I'm only including this example to show that it's technically possible with a lot of advanced Haskell features. The complexity illustrates that you're really not supposed to be doing this in "normal" Haskell code.

{-# 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]]]"

標籤：哈斯克尔

上一篇：有人可以像我5歲一樣向我解釋這些迭代器、產量單子型別和函式的含義嗎？

下一篇：Parsec的類折疊運算子