Home > other >  Haskell nested function order
Haskell nested function order

Time:01-02

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

CodePudding user response:

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]]]]
  • Related