CODEWITHSUNDEEP
haskelllist-comprehension
saulspatz
saulspatz

Reputation: 5271

Haskell List comprehension syntax

I'm trying to understand Brent Yorgey's multiset partition algorithm in the Monad.Reader Issue 8. It's been a long time since I've written any Haskell, and I guess I've forgotten even basic stuff. I'm stuck on the code in this listing:

enter image description here

I should tell you that Vec is a type alias for [Int], and that <|= means componentwise comparison of vectors:

enter image description here

The function withinFromTo is supposed to return a list of nonnegative vectors componentwise <= m, and lexicographically between s and e (inclusive).

I'm stuck on the line:

[x:xs | x <- [start, (start-1)..end]

What does [start, (start-1)..end] mean? I went to tryhaskell.org and tried evaluating [3,2..7] but it just gave me [].

I know this must seem like a stupid question, but I haven't been able to find anything by Googling, and I feel like I could read the docs for a long time before running across this.

Thanks for your help.

Upvotes: 1

Views: 748

Answers (1)

Daniel Wagner
Daniel Wagner

Reputation: 153212

The [a, b .. c] syntax is intended to make an arithmetic progression that starts with a and b, and continues until it hits c. It's probably simplest explained with a few examples:

> [3, 2 .. 0]
[3,2,1,0]
> [2, 4 .. 10]
[2,4,6,8,10]
> [3, 1 .. -10]
[3,1,-1,-3,-5,-7,-9]

The Haskell Report section on Arithmetic Sequences, together with the section on the Enum type class have the full details:

Arithmetic sequences satisfy these identities:

[ e1.. ]      = enumFrom e1
[ e1,e2.. ]   = enumFromThen e1 e2
[ e1..e3 ]    = enumFromTo e1 e3
[ e1,e2..e3 ] = enumFromThenTo e1 e2 e3

where enumFrom, enumFromThen, enumFromTo, and enumFromThenTo are class methods in the class Enum as defined in the Prelude (see Figure 6.1).

For the types Int and Integer, the enumeration functions have the following meaning:

  • The sequence enumFrom e1 is the list [e1,e1 + 1,e1 + 2,…].
  • The sequence enumFromThen e1 e2 is the list [e1,e1 + i,e1 + 2i,…], where the increment, i, is e2 − e1. The increment may be zero or negative. If the increment is zero, all the list elements are the same.
  • The sequence enumFromTo e1 e3 is the list [e1,e1 + 1,e1 + 2,…e3]. The list is empty if e1 > e3.
  • The sequence enumFromThenTo e1 e2 e3 is the list [e1,e1 + i,e1 + 2i,…e3], where the increment, i, is e2 − e1. If the increment is positive or zero, the list terminates when the next element would be greater than e3; the list is empty if e1 > e3. If the increment is negative, the list terminates when the next element would be less than e3; the list is empty if e1 < e3.

Upvotes: 6

Related Questions