Comparison of Haskell and Julia List Comprehensions | Hacker News Reader

Comparison of Haskell and Julia List Comprehensions

blog.lojic.com

82 pointstodsacerdoti55 comments

Haskell's comprehension syntax is very powerful and quite a bit more general than what is described here.

It can both be generalized to arbitrary monads through `MonadComprehension` and has extended syntax that brings in basic SQL operators (such as grouping and sorting) through `TransformListComp` as well as zipping through `ParallelListComp`.

The links are respectively https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/mona..., https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/gene..., and https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/para....

And what's more is that all three of these play very nicely with each other, so that you can write SQL-like syntax to deal with say an arbitrary, side-effectful stream rather than a finite data structure.

That means you can write something like (to take the example from the `TransformListComp` docs)

  output = [ (the dept, sum salary)
           | (name, dept, salary) <- employees
           , then group by dept using groupWith
           , then sortWith by (sum salary)
           , then take 5 ]

where `employees` is e.g. a paginated HTTP endpoint that you're hitting.

It can make for some very nice code.

Conversely, Julia's comprehension syntax is very powerful and quite a bit more general than what is described here — but in a different way.

- They're not list comprehensions, they're one-dimensional vector comprehensions. And they seamlessly extend to multidimensional array comprehensions.

- Just drop the square brackets and instead of a dense array you get a lazy generator!

Correct me if I'm wrong, but doesn't them being Monad comprehensions in Haskell automatically mean that Haskell's "list" comprehensions can be all of those things as well, and more? As well as the language's laziness by default that pretty much encompasses the generator aspect in general anyways.

(Although I'm not really trying to pit anything against each other here, they are different languages with different requirements.)

See the cousin discussion below on multidimensional arrays in Haskell.

This sounds something like transducers in Clojure, I’d be curious to see how they compare! Fascinating to see similar ideas emerging in various places. (It’s possible Clojure borrowed some concepts here as I know Rich Hickey often discusses how Haskell has solved a particular problem when discussing a Clojure approach.)

This is different from transducers in Clojure (note how `dept` and `salary` show up in multiple levels despite not being manually threaded through). This is much more similar to the way SQL syntax works.

Transducers in Haskell (and really in any language, including in Clojure) are functions of the form `a -> List b` (yes this is a fully polymorphic transducer despite the use of `List`; it can be applied to concrete data structures as well as e.g. streams of the form found in core.async, I can explain more if you're interested).

I actually think the design of transducers is a bit of a wart in Clojure. Clojure usually goes for the least powerful abstraction (so e.g. data < higher-order functions < macros), but for some reason when designing transducers decided to move away from the simple `List` based approach and instead do a Church encoding of the list to end up with a higher-order function. I wonder if it was performance related (although I'd be slightly surprised to see a higher-order function performing better)?

One of these days I hope to see a library expressing the alternative form of transducers since I find those much much easier to understand and write from scratch without pre-existing transducer generating functions.

I'm curious as to how your definition of transducer is the same as the standard one in clojure.

This is one of those times where types really make some equivalences clear that look completely unrelated at runtime.

The constructors for a list have the types

  Nil  : List a
  Cons : a -> List a -> List a

By a Church encoding (or more accurately a Boehm-Berarducci encoding) you end up with an equivalent higher order function that encodes a list of the following type:

  -- Boehm-Berarducci List
  type BBList a = forall b. b -> (b -> a -> b) -> b

I'm glossing over the details here, but you can basically squint and see how the first `b` corresponds to `nil` and the second to `cons` (and the two are truly equivalent, you can have functions going from `List a -> BBList a` and `BBList a -> List a` losslessly).

So what then let's plug `BBList` in for `List` in `a -> List b`.

  a -> List b
  -- BBList is equivalent to List
  a -> BBList b
  -- Expand out our definition of BBList
  -- We change type variables as necessary
  a -> forall c. c -> (c -> b -> c) -> c
  -- Remove a redundant forall (we can move all the way to the left)
  a -> c -> (c -> b -> c) -> c
  -- Rearrange arguments
  (c -> b -> c) -> c -> a -> c

And voila that's a tranducer (see https://news.ycombinator.com/item?id=8144385)!

Now that's how you could see at a glance from the types that they're equivalent. To understand what this means at runtime, it's helpful to think of the output list as the elements "you wish to keep" and everything not in that list as what you discard when composed with other transducers. So here's some transducers implemented in the direct list style.

  (defn duplicate [x] [x x])

  (defn keep-if-even [x] (if (even? x) [x] []))

  (defn map [f] (fn [x] [(f x)]))

The crucial thing (and why these transducers are still polymorphic) is that these collections are ephemeral: they go away in the final step of something like `into`.

Now composing this list-based transducers would require a special composition function (one that composes `a -> List b` with `b -> List c` to get `a -> List c`, basically `mapcat` in Clojure), but I actually regard that as a plus. It's always seemed like an accidental hack that transducers are composable with normal function composition. They compose "the wrong way" and you can't really compose them with normal functions anyways.

On a performance note, one of the reasons you'd want to use transducers is to reduce collection overhead, so you probably want to use transients since these are ephemeral anyways and you probably don't want to use actual vectors or actual lists. Instead you want to use collections that are heavily optimized for zero element, one element, and two element cases (as those are by far the most common situations you'll run into). With those optimizations in place you would have almost no new object/collection creation and I suspect that this will have better performance than the current higher order function-based implementation and top of that it'll be far simpler.

For a link that goes into greater detail about this see: https://stackoverflow.com/questions/26653829/how-is-a-transd...

I've also glossed over some details here so let me know if you want me to elaborate anywhere.

I really hope that this gets implemented at some point because current Clojure transducers seem like a wart in the language.

This is great. I've always been fascinated by transducers.

This use of a church encoding to generalize over strict and lazy iterations of almost arbitrary data structures and streams has been constructed and described by Oleg Kiselyov [1] long before transducers and many Haskell implementations . This page is a treasure trove of computer science theory and their applications in functional programming.

[1]: http://okmij.org/ftp/tagless-final/course/Boehm-Berarducci.h... and http://okmij.org/ftp/Streams.html

Oleg is great. In this case we're actually going the opposite direction (going back to a concrete data structure).

His stream fusion stuff is really cool, but I don't know of any popular libraries that have incorporated unfortunately. I think the Scala fs2 stream library was interested in trying to implement some of the ideas some years back, but I think they ended up not having the time or energy.

One feature I rather like in Haskell is being able to zip with list comprehension syntax[1]:

    λ> [(x, y) | x <- [1..] | y <- [1..3]]
    [(1,1),(2,2),(3,3)]

This example is a bit silly—I would just write zip [1..] [1..3]—but it makes more complex expressions involving zips much easier to read at a glance. I looked through some real code I've written, and being able to do things like this is definitely nice:

    toHashMap values = HashMap.fromList
      [ convert name value
      | name  <- Schema.fldName <$> Schema.fields t
      | value <- Vector.toList values
      ]

Of course, this particular example would be nicer if Haskell had something like dictionary comprehensions for building hash maps, but this isn't an awful substitute, and zipping multiple sequences together is useful in a lot of other configurations as well!

[1]: I should add that this requires enabling the somewhat misleadingly named `ParallelListComp` extension. Frankly, I think extensions like this should just be added to the language—this introduces new syntax, so it never changes previously valid code—but the Haskell community is very conservative about making changes to the core, standardized part of the language :/.

That actually seems confusing. I would normally expect such code to perform a Cartesian product i.e. all pairs of (x,y).

It would be a Cartesian product if the second `|` was changed to `,` (as is the case in the article and most examples in this comment section).

APL has no list comprehensions, but can generally be as clear and concise (if not more so) using ordinary array operations. Re-implemented:

  2*⍨⍳5
  1 2 3 ∘., 4 5
  (⊢,¨⊢+∘⍳1+3-⊢)¨1 2 3   ⍝ok, this one is not so hot, but apl has no primitive for x..y
  concat ← ∊             ⍝primitive
  firsts ← ⊃⍤¯1          ⍝leading-axis version
  firsts ← ⊃⍤1           ⍝trailing-axis version
  firsts ← ⊃¨            ⍝nested version
  length ← +/1⍨¨         ⍝this counts!
  factors ← ⍸0=⍳|⊢       ⍝doesn't include the number itself
  prime  ← (,1) ≡ factors
  primes ← (prime⍤0{⍺/⍵}⊢)⍳  ⍝{⍺/⍵} is a historical artefact, please ignore it
  find   ← (1⌷⊢){⍺/⍵}⍨9=0⌷⊢  ⍝{⍺/⍵} is very sorry for its repeat appearance
  pairs  ← 2 ,/ ⊢
  sorted ← ∧/ 2≤/⊢
  positions ← ⍸=
  is_lower ← {sorted ⎕ucs 'a'⍵'z'}
  lowers ← +/(is_lower⍤0)
  count  ← +/=

Note many of these are polymorphic wrt rank (or can trivially be made so), where the haskell and julia implementations only work on rank-1 ([a]) or rank-2 ([[a]]) arrays.

The Haskell one is polymorphic with respect to rank (and is indeed polymorphic even with respect to whether it's backed by a data structure or not).

Haskell's infelicities for numeric code come from other places.

For those haskell functions which operate on lists of arbitrary items, the items can indeed be themselves lists. However, the code is still fundamentally item-oriented. Those haskell functions which operate on lists of specific types (such as 'lowers', which operates on lists of characters) cannot readily be applied to higher-ranked lists of the same.

I suspect you mean `toLower`? In that case yes it can (and again generalized to many other contexts rather than just higher dimensional data structures), you just use lifted function application (that is `<$>`) instead of normal function application (that is `$`).

(The item-oriented way of thinking about this, which is equivalent, is you use `fmap`).

I mean the 'lowers' function from the linked post, which counts the lowercase characters of its input. In this case the apl function returns an array of rank one less than its input, where each item is the number of lowercase characters at the given position along the reduced axis.

I don't think this can be expressed using fmap. (I'm not sure what <$> is, but judging from [0] it seems to be syntactic sugar for fmap?) You would at least the more powerful 'reduce' (or some analogue thereof), and I'm not even sure if that would be sufficient to properly express the rank operator.

0. https://wiki.haskell.org/Functor#Related_Functions

EDIT: the problem with the rank operator is ensuring the array remains rectangular. (I know haskell lists are not rectangular; imagining a type which was.) APL punts on this by being dynamically typed, but you would have to solve that problem somehow. 'Reshape' suffers somewhat the same problem, and I'm not sure it can be typed sensibly.

Ah I see.

Right so the 0th rank version you've presented here could be written as

  -- Assume countLower exists and is [Char] -> Int

  lowers : Functor f => f [Char] -> f Int
  lowers xs = countLower <$> xs -- Also: lowers = fmap countLower

This `lowers` works for rank 0 across arbitrary rank collections so you can have as many nestings you'd like.

Now if you want to vary the rank at compile time, that is possible by generalizing `countLower` away from a concrete list and instead to something like `Traversable`.

The issue as you point out is if you want to vary the rank at runtime, which is easy to do in APL and other array-based programming languages, and which is quite difficult to do in a way that plays well with Haskell's type system (you could eject and instead use dynamic typing in Haskell instead, but that is probably going to look quite different from the rest of your Haskell code).

And this indeed is part of the infelicities I was talking about.

To really type this well you need dependent types, which you can kind of do in Haskell, but it rapidly becomes very messy.

The 'find' implementation should read:

  (1⌷⊢){⍺/⍵}⍨⊣=0⌷⊢

Julia’s syntax is the same as Python’s. It’s very natural for short expressions, a bit cumbersome for multiline comprehension, because there is no obvious way to format the code.

Another gripe I have is the order of the for clauses:

    [x for xs in xss for x in xs]

should, in my opinion, be instead written as

    [x for x in xs for xs in xss]

Also Haskell gets the order of ‘<-‘ clauses wrong, so probably mine is a minority opinion.

> Also Haskell gets the order of ‘<-‘ clauses wrong, so probably mine is a minority opinion.

That's probably so it's more in-line with do-notation:

  [x | xs <- xss, x <- xs]

is the same as:

  do { xs <- xss; x <- xs; return x }

Maybe writing statements backwards was deemed more confusing.

Personally, I don't really use list comprehension syntax, but maybe I would if they were backwards like you describe. It would make more sense with the position of the return value being to the left.

I can make sense of nested Python list comprehensions if I read them as shorthand for nested for loops, in which case you need to define variables in the outer loop before you can define dependent variables in the inner loop.

e.g. with your example above,

  for xs in xss:
      for x in xs:
          x

What's confusing about the syntax is that `x` in your example above comes first, whereas in actual nested loops it comes last. So maybe:

  [for xs in xss for x in xs : x]

Could be alternative syntax that moves `x` to the end?

That's actually how list comprehensions work in F#: that would become:

  [for xs in xss do for x in xs -> x]

(where -> is a shorthand for do yield) in practice (after 3 years of professional F#), when writing functional code i'd actually rather have the result first rather than last. I got used to reading code right to left with Haskell so that's what feels most natural to me

Note that because blocks in Julia are expressions, you can do multi-line expressions in comprehensions that you wouldn't be able to do in Python:

    [
       let y = x + 1
         z = 2y
         -z
       end 
       for x in 1:5
    ]

This specific case could be approximated with something like:

  >>> [(y:=x+1, z:= 2*y, -z)[-1] for x in range(1, 6)]
  [-4, -6, -8, -10, -12]

or, to state the obvious:

  def _(x): y = x+1; z = 2*y; return -z
  [ _(x) for x in range(1,6) ]

Haskell and Erlang basically go for mathematical notation. Python and Julia more or less go for how you read those notations.

I personally prefer math-like notation because I find it much more readable and composable.

  x, such as x is in xs, xs is in xss

  x | x ∈ xs, xs ∈ xss # my math is rusty
 
  [x | x <- xs, xs <- xss] # haskell, erlang is isimilar

  [ x for xs in xss for x in xs ] # python, julia, order might be different

As soon as you add conditions/filters on data, math-like notation wins hands down

Edit:

Since I don't know Haskell, apparently in Haskell the order is wrong. So, only Erlang gets it right (variables are upper case in Erlang):

  [ X || X <- Xs, Xs <- Xss]

> only Erlang gets it right... [ X || X <- Xs, Xs <- Xss]

I don't have much experience with Erlang, but that also seems wrong:

  1> Xss = [[1]].
  [[1]]
  2> [ X || X <- Xs, Xs <- Xss].  
  * 1:13: variable 'Xs' is unbound
  3> [ X || Xs <- Xss, X <- Xs].
  [1]

Damnit. I haven't used Erlang in a long time, but I should've known that.

So, no language does it "right".

Note that in Julia, ∈ is a synonym of `in`, so a minor improvement towards your preferred notation can be:

    [ x for xs ∈ xss for x ∈ xs ]

I'm with you on that minority opinion.

The "for" side mimics nested for loops structure, but then the output statement goes first (?!).

It's the same feel as MM/DD/YYYY date format: very widespread, yet absolutely asinine to anyone seeing it for the first time :)

I thought the same about the ordering but on the other hand this order matches what you would write in the imperative case i. e.

    for xs in xss:
        for x in xs:
            ...

after many, many years of writing python i still get this wrong at times, because i instinctively expect `[x for x in xs for xs in xss]` to be the correct version!

I appreciate where you're coming from, but this particular order allows you to reuse a variable. E.g, in earlier pythons which didn't yet have ":=", the example given by the comment below yours could be written as:

  [ z for x in range(1,6) for y in [x+1] for z in [2*y] for z in [-z] ]

Obviously not the kind of style you'd want to see in written code, but ...

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)

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.

  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?

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

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

[1] https://hackage.haskell.org/package/vector-sized-1.4.4/docs/...

> `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,

Oh! That's neat. Nesting would eliminate the need for a list at the type level, and it seems to handle numbers at the type level. That's probably sufficient to write something like a function type

  (a -> b -> c) -> Vector x a -> Vector y b -> Vector x (Vector y c)

Perhaps it can be an operator that can be chained setting the first argument to always be `(,)`.

That might roughly do what the comma does in Julia's multidimensional comprehensions.

The only bad part of this is that one wouldn't be able to define a Functor instance that works with arbitrary dimensions. It'd have to be one instance for 2 dimensions, one instance for 3 dimensions, etc.

For that, I think a list at the type level holding the dimensions would be necessary.

EDIT:

No, the nesting would prevent proper chaining mentioned operator. Using such an operator twice would result in something like `Vector z (Vector y (Vector x (a, b), c))` instead of the slightly more desirable `Vector z (Vector y (Vector x (a, (b, c)))` that I was thinking.

AFAICT, it doesn't seem that either of those suggestions is sufficient for type-safe multidimensional comprehensions in Haskell. They're better than what I found, but they still have their limitations.

Is Julia eager? In Haskell you can also do infinite lists

    [1..]

This generates all the integers. The first example

    [ x^2 | x <- [1..5] ]

Is basically already list comprehension within list comprehension. Are infinite lists possible?

Julia’s Iterators package has infinite iterators but I don’t think there’s syntax for them

If you use parens instead of brackets, you get lazy comprehensions in Julia.

I mean, the irony here for me is that I regard Haskell's list comprehensions as a bit of a bag on the side. There's not much that couldn't be equally readably implemented using other Haskell syntax.

The Raku syntax for list comprehension[0] is very similar as well.

Julia:

    [ x^2 for x = 1:5 ]

Raku:

    do $_² for 1..5;

[0]: https://docs.raku.org/language/py-nutshell#List_comprehensio...

alternatives:

  do .² for 1…5

  (1…5)»²

alternative alternative:

    do *² for 1..5;

Or:

    [ $_² for 1..5 ]

Note that in Julia these are often referred to as array comprehensions, as the data structure involved is a (very efficient) array. C.f. Python

And in Haskell they are monad comprehensions these days, so they can build more than lists. They actually used to be so back in the 90s, but Haskell 98 was conservative and restricted them to lists.

What do monad comprehensions offer?

List comprehensions are a concise way of writing do-expressions in the list monad, so monad comprehensions just extend that to all monads.

Being very generic. One can define a very efficient array structure, define its Monad instance and be able to use it in comprehensions. The point is that comprehensions are not fixed to a particular data structure by the language, and can be used with any user-definable Monad.

Reply on news.ycombinator.com