List Comprehension in Haskell, Python and Ruby

List comprehension in Haskell, Python and Ruby

For Haskell I like

let s n = sum [0,n..999] in s 3 + s 5 - s 15

or

sum $ filter ((>1).(gcd 15)) [0..999]

For fun the Rube-Goldberg version:

import Data.Bits

sum $ zipWith (*) [1..999] $ zipWith (.|.) (cycle [0,0,1]) (cycle [0,0,0,0,1])

---

Okay, explanation time.

The first version defines a little function s that sums up all multiples of n up to 999. If we sum all multiples of 3 and all multiples of 5, we included all multiples of 15 twice (once in every list), hence we need to subtract them one time.

The second version uses the fact that 3 and 5 are primes. If a number contains one or both of the factors 3 and 5, the gcd of this number and 15 will be 3, 5 or 15, so in every case the gcd will be bigger than one. For other numbers without a common factor with 15 the gcd becomes 1. This is a nice trick to test both conditions in one step. But be careful, it won't work for arbitrary numbers, e.g. when we had 4 and 9, the test gdc x 36 > 1 won't work, as gcd 6 36 == 6, but neither mod 6 4 == 0 nor mod 6 9 == 0.

The third version is quite funny. cycle repeats a list over and over. cycle [0,0,1] codes the "divisibility pattern" for 3, and cycle [0,0,0,0,1] does the same for 5. Then we "or" both lists together using zipWith, which gives us [0,0,1,0,1,1,0,0,1,1,0,1...]. Now we use zipWith again to multiply this with the actual numbers, resulting in [0,0,3,0,5,6,0,0,9,10,0,12...]. Then we just add it up.

Knowing different ways to do the same thing might be wasteful for other languages, but for Haskell it is essential. You need to spot patterns, pick up tricks and idioms, and play around a lot in order to gain the mental flexibility to use this language effectively. Challenges like the project Euler problems are a good opportunity to do so.

List comprehension in Ruby

If you really want to, you can create an Array#comprehend method like this:

class Array
  def comprehend(&block)
    return self if block.nil?
    self.collect(&block).compact
  end
end

some_array = [1, 2, 3, 4, 5, 6]
new_array = some_array.comprehend {|x| x * 3 if x % 2 == 0}
puts new_array

Prints:

6
12
18

I would probably just do it the way you did though.

Python list comprehension = Ruby select / reject on index rather than element

The method order is relevant:

arr.each_with_index.select { |e, i| i % 3 == 0 }
#=> [[10, 0], [40, 3], [70, 6], [100, 9]]

versus:

arr.select.each_with_index { |e, i| i % 3 == 0 }
#=> [10, 40, 70, 100]

Since select returns an enumerator, you could also use Enumerator#with_index:

arr.select.with_index { |e, i| i % 3 == 0 }
#=> [10, 40, 70, 100]

Regarding your slice equivalent, you can use map (or its alias collect) to collect the items in an array:

(0..arr.length).step(3).map { |e| arr[e] }
#=> [10, 40, 70, 100]

or values_at to fetch the items at the given indices:

arr.values_at(*(0..arr.length).step(3))
#=> [10, 40, 70, 100]

* turns the argument into an array (via to_a) and then into an argument list, i.e.:

arr.values_at(*(0..arr.length).step(3))
arr.values_at(*(0..arr.length).step(3).to_a)
arr.values_at(*[0, 3, 6, 9])
arr.values_at(0, 3, 6, 9)

Slightly shorter:

arr.values_at(*0.step(arr.size, 3))
#=> [10, 40, 70, 100]

Python: List Comprehension and Functional Programming

If your question is "give me some examples that show how FP works in python", then :

What is pure Functional Programming (in Python)?

It is a programming paradigm that avoids state and mutable data and instead relies on function return values. This means a purely functional program written in python will not have things like variables, states etc.

Not so pure FP

You can combine the FP and imperative paradigm, and with good results (see here). The linked gist is a math quiz program I made for a python class I took some months ago. Feel free to do whatever you want with the code.

FP in Java/C#

I personally have no experience with C# so someone else would need to post a C# example, but you can have FP in Java, but not pure FP. Example :

int fib (int x) { 
    if (x < 2) return x;
    return fib (x-1) + fib(x-2);
}

The method above is completely FP, but it cannot be used in a pure FP context when using Java. This needs to be put inside of a class C in Java, and can only be called after you have instantiated an object of that type. This last part disqualifies the Java class C from being FP, but the method will still be.

Edit : actually, you can have static methods in Java which can be used without any instantiation. So if you change the signature to static int fib (int x) , then the method and it's method calls might still be FP if called in a FP-manner.

---

Re : your comment

Recursion may be FP, but it does not have to be (see below):

def f(first, rest):
    print first
    first = rest[0]; rest = rest[1:]
    f(first, rest)

You can also have FP without recursion :

 def sum (a,b):
     return a+b

 def square(c):
     return c*c

 def square_of_sum (x,y):
     return square(sum(x,y))

Erlang vs Ruby list comprehensions

First off, your data structures aren't equivalent. The equivalent Ruby data structure to your Erlang example would be more like

weather = [[:toronto, :rain], [:montreal, :storms], [:london, :fog], 
            [:paris, :sun], [:boston, :fog], [:vancouver, :snow]]

Secondly, yes, Ruby doesn't have list comprehensions nor pattern matching. So, the example will probably be more complex. Your list comprehension first filters all foggy cities, then projects the name. Let's do the same in Ruby:

weather.select {|_, weather| weather == :fog }.map(&:first)
# => [:london, :boston]

However, Ruby is centered around objects, but you are using abstract data types. With a more object-oriented data abstraction, the code would probably look more like

weather.select(&:foggy?).map(&:city)

which isn't too bad, is it?

Idiomatic way to have many of the same generators in a list comprehension

If your concern is the [1..6] repetition (the ability for the range to vary independently), you could use:

let die = [1..6] in [ (d1,d2,d3,d4) | d1 <- die, d2 <- die
                                    , d3 <- die, d4 <- die
                                    , (d1 + d2 + d3 + d4) == 10 ]

Overall, to remove the explicit die naming, while this isn't exactly the same since it will be lists instead of tuples:

let die = [1..6] in [dice | dice <- sequence (replicate 4 die), sum dice == 10]

To recover the tuples you could pattern match, but that might introduce difficult to trace bugs if the input expression changes as pattern match failure will simply exclude the element:

let die = [1..6] in
  [ (d1,d2,d3,d4) | dice@[d1,d2,d3,d4] <- sequence (replicate 4 die)
                  , sum dice == 10 ]

List Comprehension in an Open Office Spreadsheet

CountIf can count values equal to one chosen. Unfortunately it seems that there is no good candidate for such function. Alternatively you can use additional column with If to display 1 or 0 if the value fits in range or not accordingly:

=If(AND({list_cell}>=MinVal; {list_cell}<=MaxVal); 1; 0)

Then only thing left is to sum up this additional column.

Why Haskell list comprehension is faster than loop

First some style advice:

lg s e a
  | s >= e     = a
  | even s     = lg (s+1) e (a+1)
  | otherwise  = lg (s+1) e (a*2)

Regarding your question: lg is not really a loop. It's a tail-recursive function, but that alone doesn't say much in Haskell. The main thing that gets in the way is lazyness: if the accumulators are only accumulated in the thunk-dimension, rather than their values, lazyness merely builds up an enourmous amount of overhead without any usability gain.

A simple way to prevent this is to evaluate arguments strictly, with

{-# LANGUAGE BangPatterns     #-}

lg' s e !a
  | s >= e     = a
  | even s     = lg' (s+1) e (a+1)
  | otherwise  = lg' (s+1) e (a*2)

However, because of such issues but also because of conciseness/modularity/..., it is rather preferred not to write tail-recursive functions at all but use higher level-tools – list comprehensions themselves are often not that great performance-wise, but if you express your algorithms in terms of generic folds etc. you can utilise much more performant data structures such as unboxed vectors with little changes to your code.

---

Related Topics