2

我正在尝试在 Haskell 中编写一个函数来生成多维列表。

（从技术上讲，我使用的是 Curry，但我的理解是它主要是 Haskell 的超集，而我正在尝试做的事情对 Haskell 来说也很常见。）

经过一番挠头后，我意识到我最初想要的函数（m_array generating_function list_of_dimensions，给一个嵌套深度等于的列表length list_of_dimensions）可能与它们的类型系统本身不一致，因为（AFAICT）列表的嵌套深度是它的一部分类型，我的函数想要返回嵌套深度根据参数值而不同的值，这意味着它想要返回类型根据值而变化的值Haskell 不支持 (AFAICT) 的参数。（如果我错了，这可以做到，请告诉我。）此时我转到下一段，但如果有一个我错过的解决方法，它采用非常相似的参数并且仍然输出一个嵌套列表，让我知道。就像，也许如果您可以将索引编码为某种数据类型，该数据类型在其类型中隐含包含嵌套级别，并用 eg 实例化dimensions 5 2 6 ...，那可能可行吗？没有把握。

无论如何，我认为也许我可以通过嵌套函数本身来编码嵌套深度，同时仍然保持参数可管理。这确实有效，我最终得到以下结果：

ma f (l:ls) idx = [f ls (idx++[i]) | i <- [0..(l-1)]]

但是，到目前为止，使用起来还是有点笨拙：您需要嵌套调用，例如

ma (ma (ma (\_ i -> 0))) [2,2,2] []

（顺便说一句，它给出了[[[0,0],[0,0]],[[0,0],[0,0]]]。如果你使用(\_ i -> i)，它会用相应元素的索引填充数组，这是我想保持可用的结果，但可能是一个令人困惑的例子。）

我宁愿尽量减少必要的样板文件。如果我不能打电话

ma (\_ i -> i) [2,2,2]

我希望能够打电话，最坏的情况，

ma ma ma (\_ i -> i) [2,2,2] []

但如果我尝试这样做，我会得到错误。据推测，参数列表的划分方式对函数没有意义。我花了大约半个小时的谷歌搜索和实验，试图找出 Haskell 解析此类函数字符串的机制，但我还没有找到明确的解释，理解也难以理解。所以，正式的问题：

  1. Haskell 如何解析 eg f1 f2 f3 x y z？参数是如何分配的？它是依赖于函数的签名，还是只是尝试f1使用 5 个参数调用？
  2. 有没有一种重组ma方法允许在没有括号的情况下调用它？（最多允许添加两个辅助函数，例如maStart ma ma maStop (\_ i -> i) [1,2,3,4] []，如有必要。）
4

2 回答 2

3

您在令人头疼的段落中想要的功能是可以直接实现的——尽管有点吵。使用GADTs和DataKinds，可以通过数字参数化值。您将无法直接使用列表，因为它们没有在类型中提及它们的长度，但是一个简单的变体确实很好用。这是它的外观。

{-# Language DataKinds #-}
{-# Language GADTs #-}
{-# Language ScopedTypeVariables #-}
{-# Language StandaloneDeriving #-}
{-# Language TypeOperators #-}

import GHC.TypeLits

infixr 5 :+

data Vec n a where
    O :: Vec 0 a -- O is supposed to look a bit like a mix of 0 and []
    (:+) :: a -> Vec n a -> Vec (n+1) a

data FullTree n a where
    Leaf :: a -> FullTree 0 a
    Branch :: [FullTree n a] -> FullTree (n+1) a

deriving instance Show a => Show (Vec n a)
deriving instance Show a => Show (FullTree n a)

ma :: forall n a. ([Int] -> a) -> Vec n Int -> FullTree n a
ma f = go [] where
    go :: [Int] -> Vec n' Int -> FullTree n' a
    go is O = Leaf (f is)
    go is (l :+ ls) = Branch [go (i:is) ls | i <- [0..l-1]]

在 ghci 中尝试一下：

> ma (\_ -> 0) (2 :+ 2 :+ 2 :+ O)
Branch [Branch [Branch [Leaf 0,Leaf 0],Branch [Leaf 0,Leaf 0]],Branch [Branch [Leaf 0,Leaf 0],Branch [Leaf 0,Leaf 0]]]
> ma (\i -> i) (2 :+ 2 :+ 2 :+ O)
Branch [Branch [Branch [Leaf [0,0,0],Leaf [1,0,0]],Branch [Leaf [0,1,0],Leaf [1,1,0]]],Branch [Branch [Leaf [0,0,1],Leaf [1,0,1]],Branch [Leaf [0,1,1],Leaf [1,1,1]]]]
于 2021-12-31T20:26:28.737 回答
2

低技术解决方案：

在 Haskell 中，您可以使用所谓的free monad对多级列表进行建模。基本定义是：

data Free ft a = Pure a | Free (ft (Free ft a))

whereft可以是任何函子，但在这里我们感兴趣的ft是[]，即列表函子。所以我们像这样定义我们的多维列表：

import  Control.Monad
import  Control.Monad.Free

type Mll = Free []  -- Multi-Level List

Mll类型转换器恰好是Functor, Foldable,Traversable类的一个实例，它可以派上用场。

为了制作一个任意维度的数组，我们从以下开始：

  1. 维度列表，例如 [5,2,6]
  2. 填充函数，它为给定的一组索引返回一个值

我们可以从创建一个“网格”对象开始，它的索引项说 [x,y,z] 正是 [x,y,z] 列表。由于我们有一个仿函数实例，我们可以通过应用fmap filler到我们的网格对象来完成这个过程。

这给出了以下代码：

makeNdArray :: ([Int] -> a) -> [Int] -> Mll a
makeNdArray filler dims =
   let
       addPrefix x (Pure xs)   =  Pure (x:xs)
       addPrefix x (Free xss)  =  Free $ map (fmap (x:)) xss
       makeGrid []      =  Pure []
       makeGrid (d:ds)  =  let  base = 0
                                fn k = addPrefix k (makeGrid ds)
                           in   Free $ map fn [base .. (d-1+base)]
       grid             = makeGrid dims
   in
       fmap filler grid  -- because we are an instance of the Functor class

为了可视化生成的结构，删除构造函数名称很方便：

displayMll :: Show a => Mll a -> String
displayMll = filter (\ch -> not (elem ch "Pure Free")) . show

如果需要，生成的结构可以很容易地展平：

toListFromMll :: Mll a -> [a]
toListFromMll xs  =  foldr (:) [] xs

sum对于数字基类型，我们可以“免费”获得一个多维函数，可以这么说：

mllSum :: Num a => (Mll a) -> a
mllSum = sum  -- because we are an instance of the Foldable class
              -- or manually: foldr (+) 0

一些实践：

我们使用 [5,2,6] 作为维度集。为了可视化结构，我们将一个十进制数字与每个索引相关联。我们可以通过添加 111 来假装具有 1 基索引，因为这样所有生成的数字都是 3 位长，这使得结果更容易检查。手动添加额外的换行符。

$ ghci
 GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
 λ> 
 λ> dims = [5,2,6]
 λ> filler = \[x,y,z] -> (100*x + 10*y + z + 111)
 λ> 
 λ> mxs = makeNdArray filler dims
 λ> 
 λ> displayMll mxs
 "[[[111,112,113,114,115,116],[121,122,123,124,125,126]],
   [[211,212,213,214,215,216],[221,222,223,224,225,226]],
   [[311,312,313,314,315,316],[321,322,323,324,325,326]],
   [[411,412,413,414,415,416],[421,422,423,424,425,426]],
   [[511,512,513,514,515,516],[521,522,523,524,525,526]]]"
 λ>

如上所述，我们可以将结构展平：

 λ> 
 λ> xs = toListFromMll mxs
 λ> xs
  [111,112,113,114,115,116,121,122,123,124,125,126,211,212,213,214,215,216,221,222,223,224,225,226,311,312,313,314,315,316,321,322,323,324,325,326,411,412,413,414,415,416,421,422,423,424,425,426,511,512,513,514,515,516,521,522,523,524,525,526]
 λ>

或取其总和：

 λ> 
 λ> sum mxs
 19110
 λ> 
 λ> sum xs
 19110
 λ> 
 λ> 
 λ> length mxs
 60
 λ> 
 λ> length xs
 60
 λ>
于 2022-01-04T21:07:59.750 回答