Haskell 嵌套函数顺序

Haskell nested function order

我正在尝试在 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 解析这样的函数字符串的机制,但我没有找到明确的解释,而且我无法理解。所以,正式问题:

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

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

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

低技术含量的解决方案:

在 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型变压器恰好是FunctorFoldableTraversable类的一个实例,它可以派上用场。

要创建任意维度的数组,我们从:

开始
  1. 维度列表,例如[5,2,6]
  2. 填充函数,其中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
 λ>