Haskell 嵌套函数顺序

Question

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

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

经过一番挠头，我意识到我最初想要的功能（m_array generating_function list_of_dimensions，给出一个嵌套深度等于 length list_of_dimensions 的列表）可能与它们类型系统本身不一致，因为（AFAICT）列表的嵌套深度是其类型的一部分，而我的函数想要 return 嵌套深度因参数值而异的值，这意味着它想要 return types 根据参数的 value 变化的值，Haskell 不支持（AFAICT）。（如果我错了，并且这可以完成，请告诉我。）在这一点上我继续下一段，但是如果我错过了一个变通方法，它采用非常相似的参数并且仍然输出一个嵌套列表，让我知道。就像，也许如果您可以将索引编码为某种数据类型，该数据类型在其类型中隐式包含嵌套级别，并使用例如实例化。 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 解析这样的函数字符串的机制，但我没有找到明确的解释，而且我无法理解。所以，正式问题：

Haskell 如何解析例如f1 f2 f3 x y z？如何分配参数？它是依赖于函数的签名，还是依赖于函数的签名？试着用 5 个参数调用 f1?
是否有重组 ma 以允许不带括号调用它的方法？（最多允许添加两个辅助函数，例如 maStart ma ma maStop (\_ i -> i) [1,2,3,4] []，如有必要。）

Answer 1

您在令人头疼的段落中想要的功能可以直接实现——尽管有点吵。使用 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]]]]

Answer 2

低技术含量的解决方案：

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

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

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

import  Control.Monad
import  Control.Monad.Free

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

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

要创建任意维度的数组，我们从：

开始

维度列表，例如[5,2,6]
填充函数，其中returns给定索引集的值

我们可以从创建一个“网格”对象开始，其索引项 [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
 λ>

Haskell 嵌套函数顺序

Haskell nested function order

haskell

multidimensional-array

functional-programming

dependent-type

curry

低技术含量的解决方案：

一些练习：