Haskell nested function order

Question

I'm trying to write a function in Haskell to generate multidimensional lists.

(Technically I'm using Curry, but my understanding is that it's mostly a superset of Haskell, and the thing I'm trying to do is common to Haskell as well.)

After a fair bit of head scratching, I realized my initial desired function (m_array generating_function list_of_dimensions, giving a list nested to a depth equal to length list_of_dimensions) was probably at odds with they type system itself, since (AFAICT) the nesting-depth of lists is part of its type, and my function wanted to return values whose nesting-depths differed based on the value of a parameter, meaning it wanted to return values whose types varied based on the value of a parameter, which (AFAICT) isn't supported in Haskell. (If I'm wrong, and this CAN be done, please tell me.) At this point I moved on to the next paragraph, but if there's a workaround I've missed that takes very similar parameters and still outputs a nested list, let me know. Like, maybe if you can encode the indices as some data type that implicitly includes the nesting level in its type, and is instantiated with e.g. dimensions 5 2 6 ..., maybe that'd work? Not sure.

In any case, I thought that perhaps I could encode the nesting-depth by nesting the function itself, while still keeping the parameters manageable. This did work, and I ended up with the following:

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

However, so far it's still a little clunky to use: you need to nest the calls, like

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

(which, btw, gives [[[0,0],[0,0]],[[0,0],[0,0]]]. If you use (\_ i -> i), it fills the array with the indices of the corresponding element, which is a result I'd like to keep available, but could be a confusing example.)

I'd prefer to minimize the boilerplate necessary. If I can't just call

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

I'd LIKE to be able to call, at worst,

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

But if I try that, I get errors. Presumably the list of parameters is being divvied up in a way that doesn't make sense for the function. I've spent about half an hour googling and experimenting, trying to figure out Haskell's mechanism for parsing strings of functions like that, but I haven't found a clear explanation, and understanding eludes me. So, the formal questions:

1. How does Haskell parse e.g. f1 f2 f3 x y z? How are the arguments assigned? Is it dependent on the signatures of the functions, or does it e.g. just try to call f1 with 5 arguments?
2. Is there a way of restructuring ma to permit calling it without parentheses? (Adding at most two helper functions would be permissible, e.g. maStart ma ma maStop (\_ i -> i) [1,2,3,4] [], if necessary.)

Answer 1

The function you want in your head-scratching paragraph is possible directly -- though a bit noisily. With GADTs and DataKinds, values can be parameterized by numbers. You won't be able to use lists directly, because they don't mention their length in their type, but a straightforward variant that does works great. Here's how it looks.

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

Try it out in 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

A low-tech solution:

In Haskell, you can model multi-level lists by using the so-called free monad. The base definition is:

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

where ft can be any functor, but here we are interested in ft being [], that is the list functor. So we define our multidimensional list like this:

import  Control.Monad
import  Control.Monad.Free

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

The Mll type transformer happens to be an instance of the Functor, Foldable, Traversable classes, which can come handy.

To make an array of arbitrary dimension, we start with:

1. the list of dimensions, for example [5,2,6]
2. the filler function, which returns a value for a given set of indices

We can start by making a “grid” object, whose item at indices say [x,y,z] is precisely the [x,y,z] list. As we have a functor instance, we can complete the process by just applying fmap filler to our grid object.

This gives the following code:

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

To visualize the resulting structure, it is handy to be able to remove the constructor names:

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

The resulting structure can easily be flattened if need be:

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

For numeric base types, we can get a multidimensional sum function “for free”, so to speak:

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

Some practice:

We use [5,2,6] as the dimension set. To visualize the structure, we associate a decimal digit to every index. We can pretend to have 1-base indexing by adding 111, because that way all the resulting numbers are 3 digits long, which makes the result easier to check. Extra newlines added manually.

$ 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]]]"
 λ> 

As mentioned above, we can flatten the structure:

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

or take its overall sum:

 λ> 
 λ> sum mxs
 19110
 λ> 
 λ> sum xs
 19110
 λ> 
 λ> 
 λ> length mxs
 60
 λ> 
 λ> length xs
 60
 λ>