List comprehension in haskell with let and show, what is it for?

4
votes

I'm studying project euler solutions and this is the solution of problem 4, which asks to

Find the largest palindrome made from the product of two 3-digit numbers

problem_4 =
  maximum [x | y<-[100..999], z<-[y..999], let x=y*z, let s=show x, s==reverse s]

I understand that this code creates a list such that x is a product of all possible z and y.

However I'm having a problem understanding what does s do here. Looks like everything after | is going to be executed everytime a new element from this list is needed, right?

I don't think I understand what's happening here. Shouldn't everything to the right of | be constraints?

2
haskelllist-comprehension
x is the product of all possible z, y? Now it aims to construct products that are palindromes. – Willem Van Onsem
@WillemVanOnsem I meant that the list would have all the products but anyways I think even this interpretation is wrong – user6791424
x is the product of all possible y and z where z >= y and x is a palindrome (that is what s does). The maximum of the list is the largest palindrome of such products. – George Co

2 Answers

5
votes

A list comprehension is a rather thin wrapper around a do expression:

problem_4 = maximum $ do
     y <- [100..999]
     z <- [y..999]
     let x = y*z
     let s = show x
     guard $ s == reverse s
     return x

Most pieces translate directly; pieces that aren't iterators (<-) or let expressions are treated as arguments to the guard function found in Control.Monad. The effect of guard is to short-circuit the evaluation; for the list monad, this means not executing return x for the particular value of x that led to the false argument.

5
votes

I don't think I understand what's happening here. Shouldn't everything to the right of | be constraints?

No, at the right part you see an expression that is a comma-separated (,) list of "parts", and every part is one of the following tree:

  1. an "generator" of the form somevar <- somelist;
  2. a let statement which is an expression that can be used to for instance introduce a variable that stores a subresult; and
  3. expressions of the type boolean that act like a filter.

So it is not some sort of "constraint programming" where one simply can list some constraints and hope that Haskell figures it out (in fact personally that is the difference between a "programming language" and a "specification language": in a programming language you have "control" how the data flows, in a specification language, that is handled by a system that reads your specifications)

Basically an iterator can be compared to a "foreach" loop in many imperative programming languages. A "let" statement can be seen as introducing a temprary variable (but note that in Haskell you do not assign variable, you declare them, so you can not reassign values). The filter can be seen as an if statement.

So the list comprehension would be equivalent to something in Python like:

for y in range(100, 1000):
    for z in range(y, 1000):
        x = y * z
        s = str(x)
        if x == x[::-1]:
            yield x

We thus first iterate over two ranges in a nested way, then we declare x to be the multiplication of y and z, with let s = show x, we basically convert a number (for example 15129) to its string counterpart (for example "15129"). Finally we use s == reverse s to reverse the string and check if it is equal to the original string.

Note that there are more efficient ways to test Palindromes, especially for multiplications of two numbers.