4 ms·

Are there multidimensional comprehensions in Haskell? In Julia you have jl> [ (x,y) for x in 1:3, y in 2:5 ] 3×4 Matrix{Tuple{Int64, Int64}}: (1, 2)

by DNF2 5y ago

Are there multidimensional comprehensions in Haskell? In Julia you have jl> [ (x,y) for x in 1:3, y in 2:5 ] 3×4 Matrix{Tuple{Int64, Int64}}: (1, 2) (1, 3) (1, 4) (1, 5) (2, 2) (2, 3) (2, 4) (2, 5) (3, 2) (3, 3) (3, 4) (3, 5)

jolmg 5y ago
You can have them if you can define Matrix as a data structure with a Monad instance. I don't know if there are any packages that do something like that. Maybe something roughly like this: data Matrix a = Matrix { matrixDimensions :: [Int] , matrixCells :: [a] } deriving (Show) fromList :: [a] -> Matrix a fromList xs = Matrix [length xs] xs instance Functor Matrix where fmap f (Matrix dims xs) = Matrix dims $ fmap f xs instance Applicative Matrix where pure x = Matrix [] [x] Matrix fds fs <*> Matrix xds xs = Matrix (fds ++ xds) (fs <*> xs) instance Monad Matrix where Matrix ds xs >>= f = Matrix (ds ++ rds) rs where Matrix rds rs = case f <$> xs of [] -> Matrix [] [] ms@(Matrix frds _:_) -> Matrix frds (concat $ matrixCells <$> ms) ghci> [(x, y) | x <- fromList [1..3], y <- fromList [2..5] ] Matrix {matrixDimensions = [3,4], matrixCells = [(1,2),(1,3),(1,4),(1,5),(2,2),(2,3),(2,4),(2,5),(3,2),(3,3),(3,4),(3,5)]} If you want it to be pretty printed into a nice-looking table, you can define your own Show instance. This is probably not the best way to implement it, though. Notice that I use the first Matrix returned by `f` in the Monad instance definition and assume that all subsequent matrices are of the same dimensions. The problem with fixing that is that we'd have to fix the dimensions into the type and that would prevent us from writing a Monad instance that would work for your example. I don't know Julia, but I think the reason why this is not a problem for it is because neither x nor y are in scope for each other's definition: julia> [ (x,y) for x in 1:3, y in 1:x ] ERROR: UndefVarError: x not defined Stacktrace: [1] top-level scope @ REPL[1]:1 julia> [ (x,y) for x in 1:y, y in 1:3 ] ERROR: UndefVarError: y not defined Stacktrace: [1] top-level scope @ REPL[2]:1 while x would be in scope for y's definition in Haskell, allowing the y dimension to vary by value of x. I guess the best one can do in terms of safety for that case is turn it into a runtime error in Haskell. If one wants to handle Matrices with better type-safety it's probably best to give up on comprehensions for it, make the Matrix type more descriptive, and use other operators.
- DNF2 5y ago
  julia> [ (x,y) for x in 1:3, y in 1:x ] ERROR: UndefVarError: x not defined I think the reason for having x and y in different scopes like this is that if the range of y depended on the value of x, this wouldn't turn into an array, where you need all dimensions to have regular length. BTW, this extends to arbitrary dimensions. I take it multidimensional arrays aren't common data structures in Haskell?
  - jolmg 5y ago
    > if the range of y depended on the value of x, this wouldn't turn into an array, where you need all dimensions to have regular length Yes, that's the issue I encountered with the Monad definition. Had to handle the case where y varied, while in the Julia expression that wasn't possible. I thought the comma in Julia's: [ (x,y) for x in 1:3, y in 2:5 ] was like the comma in Haskell's: [ (x,y) | x <- [1..3], y <- [2..5] ] but I see now that the above Haskell expression is actually the following Julia: [ (x,y) for x in 1:3 for y in 2:5 ] > I take it multidimensional arrays aren't common data structures in Haskell? Nope. They're not a core type in the language, and while I did see some packages on a quick search, they unfortunately seem pretty limited. They're either limited to 2 dimensions or low lengths per dimension. Part of the issue is probably that it'd be for the best for the dimensions to be specified in the type signature, in order to make stuff like adding 2 matrices of different dimensions a compile-time error. However, that gets complicated because you have to use numbers in type signatures and also be able to express a variable number of them. It might be workable using the DataKinds extension and 2-tuple type constructors as cons cells, but it sounds messy. Things get a lot simpler if that's just forgotten about and such errors are raised at run-time, but that's just not what one typically strives for when writing Haskell. Tracing bugs from errors raised at run-time is also quite more troublesome than from those raised at compile-time.
    - nybble41 5y ago
      >> I take it multidimensional arrays aren't common data structures in Haskell? > Nope. They're not a core type in the language, and while I did see some packages on a quick search, they unfortunately seem pretty limited. They're either limited to 2 dimensions or low lengths per dimension. The Data.Array module from the `array` package[0] provides arrays for arbitrary "index" types implementing the Ix interface, which includes tuples of arbitrary Ix types for multi-dimensional arrays. Instances of Ix are defined generically for tuples of up to five elements (for five-dimensional arrays) but you can always define more (orphan) instances, or use a custom Ix type with more than five parameters, or even nest tuples so that your index looks like ((a, b, c), (d, e, f), (g, h, i)), which I believe would be equivalent to the 9-tuple index (a, b, c, d, e, f, g, h, i). For vectors with sizes determined at the type level you have Data.Vector.Sized from the `vector-sized` package[1]. This does not directly support multi-dimensional indices as the size type parameter must be of kind KnownNat, but they can be nested, and the type-level size information implies that all the nested vectors will be the same length. [0] https://hackage.haskell.org/package/array-0.5.4.0/docs/Data-Array.html https://hackage.haskell.org/package/array-0.5.4.0/docs/Data-... [1] https://hackage.haskell.org/package/vector-sized-1.4.4/docs/Data-Vector-Sized.html https://hackage.haskell.org/package/vector-sized-1.4.4/docs/...

by DNF2 5y ago

jolmg 5y ago

You can have them if you can define Matrix as a data structure with a Monad instance. I don't know if there are any packages that do something like that. Maybe something roughly like this: data Matrix a = Matrix { matrixDimensions :: [Int] , matrixCells :: [a] } deriving (Show) fromList :: [a] -> Matrix a fromList xs = Matrix [length xs] xs instance Functor Matrix where fmap f (Matrix dims xs) = Matrix dims $ fmap f xs instance Applicative Matrix where pure x = Matrix [] [x] Matrix fds fs <*> Matrix xds xs = Matrix (fds ++ xds) (fs <*> xs) instance Monad Matrix where Matrix ds xs >>= f = Matrix (ds ++ rds) rs where Matrix rds rs = case f <$> xs of [] -> Matrix [] [] ms@(Matrix frds _:_) -> Matrix frds (concat $ matrixCells <$> ms) ghci> [(x, y) | x <- fromList [1..3], y <- fromList [2..5] ] Matrix {matrixDimensions = [3,4], matrixCells = [(1,2),(1,3),(1,4),(1,5),(2,2),(2,3),(2,4),(2,5),(3,2),(3,3),(3,4),(3,5)]} If you want it to be pretty printed into a nice-looking table, you can define your own Show instance. This is probably not the best way to implement it, though. Notice that I use the first Matrix returned by `f` in the Monad instance definition and assume that all subsequent matrices are of the same dimensions. The problem with fixing that is that we'd have to fix the dimensions into the type and that would prevent us from writing a Monad instance that would work for your example. I don't know Julia, but I think the reason why this is not a problem for it is because neither x nor y are in scope for each other's definition: julia> [ (x,y) for x in 1:3, y in 1:x ] ERROR: UndefVarError: x not defined Stacktrace: [1] top-level scope @ REPL[1]:1 julia> [ (x,y) for x in 1:y, y in 1:3 ] ERROR: UndefVarError: y not defined Stacktrace: [1] top-level scope @ REPL[2]:1 while x would be in scope for y's definition in Haskell, allowing the y dimension to vary by value of x. I guess the best one can do in terms of safety for that case is turn it into a runtime error in Haskell. If one wants to handle Matrices with better type-safety it's probably best to give up on comprehensions for it, make the Matrix type more descriptive, and use other operators.

DNF2 5y ago
julia> [ (x,y) for x in 1:3, y in 1:x ] ERROR: UndefVarError: x not defined I think the reason for having x and y in different scopes like this is that if the range of y depended on the value of x, this wouldn't turn into an array, where you need all dimensions to have regular length. BTW, this extends to arbitrary dimensions. I take it multidimensional arrays aren't common data structures in Haskell?
- jolmg 5y ago
  > if the range of y depended on the value of x, this wouldn't turn into an array, where you need all dimensions to have regular length Yes, that's the issue I encountered with the Monad definition. Had to handle the case where y varied, while in the Julia expression that wasn't possible. I thought the comma in Julia's: [ (x,y) for x in 1:3, y in 2:5 ] was like the comma in Haskell's: [ (x,y) | x <- [1..3], y <- [2..5] ] but I see now that the above Haskell expression is actually the following Julia: [ (x,y) for x in 1:3 for y in 2:5 ] > I take it multidimensional arrays aren't common data structures in Haskell? Nope. They're not a core type in the language, and while I did see some packages on a quick search, they unfortunately seem pretty limited. They're either limited to 2 dimensions or low lengths per dimension. Part of the issue is probably that it'd be for the best for the dimensions to be specified in the type signature, in order to make stuff like adding 2 matrices of different dimensions a compile-time error. However, that gets complicated because you have to use numbers in type signatures and also be able to express a variable number of them. It might be workable using the DataKinds extension and 2-tuple type constructors as cons cells, but it sounds messy. Things get a lot simpler if that's just forgotten about and such errors are raised at run-time, but that's just not what one typically strives for when writing Haskell. Tracing bugs from errors raised at run-time is also quite more troublesome than from those raised at compile-time.
  - nybble41 5y ago
    >> I take it multidimensional arrays aren't common data structures in Haskell? > Nope. They're not a core type in the language, and while I did see some packages on a quick search, they unfortunately seem pretty limited. They're either limited to 2 dimensions or low lengths per dimension. The Data.Array module from the `array` package[0] provides arrays for arbitrary "index" types implementing the Ix interface, which includes tuples of arbitrary Ix types for multi-dimensional arrays. Instances of Ix are defined generically for tuples of up to five elements (for five-dimensional arrays) but you can always define more (orphan) instances, or use a custom Ix type with more than five parameters, or even nest tuples so that your index looks like ((a, b, c), (d, e, f), (g, h, i)), which I believe would be equivalent to the 9-tuple index (a, b, c, d, e, f, g, h, i). For vectors with sizes determined at the type level you have Data.Vector.Sized from the `vector-sized` package[1]. This does not directly support multi-dimensional indices as the size type parameter must be of kind KnownNat, but they can be nested, and the type-level size information implies that all the nested vectors will be the same length. [0] https://hackage.haskell.org/package/array-0.5.4.0/docs/Data-Array.html https://hackage.haskell.org/package/array-0.5.4.0/docs/Data-... [1] https://hackage.haskell.org/package/vector-sized-1.4.4/docs/Data-Vector-Sized.html https://hackage.haskell.org/package/vector-sized-1.4.4/docs/...