CODEWITHSUNDEEP
haskelllist-comprehension
Aeveus
Aeveus

Reputation: 5382

Setting upper limit to the input set according to the output function

I'm currently stuck on setting upper limits in list comprehensions.

What I'm trying to do is to find all Fibonacci numbers below one million. For this I had designed a rather simple recursive Fibonacci function

fib :: Int -> Integer
fib n
    n == 0    = 0
    n == 1    = 1
    otherwise = fib (n-1) + fib (n-2)

The thing where I'm stuck on is defining the one million part. What I've got now is:

[ fib x | x <- [0..35], fib x < 1000000 ]

This because I know that the 35th number in the Fibonacci sequence is a high enough number. However, what I'd like to have is to find that limit via a function and set it that way.

[ fib x | x <- [0..], fib x < 1000000 ]

This does give me the numbers, but it simply doesn't stop. It results in Haskell trying to find Fibonacci numbers below one million further in the sequence, which is rather fruitless.

Could anyone help me out with this? It'd be much appreciated!

Upvotes: 3

Views: 412

Answers (4)

Landei
Landei

Reputation: 54584

It should be mentioned that for such a task the "canonical" (and faster) way is to define the numbers as an infinite stream, e.g.

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

takeWhile (<100) fibs
--[0,1,1,2,3,5,8,13,21,34,55,89]

The recursive definition may look scary (or even "magic") at first, but if you "think lazy", it will make sense.

A "loopy" (and in a sense more "imperative") way to define such an infinite list is:

fibs = map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)

[Edit]

For an efficient direct calculation (without infinite list) you can use matrix multiplication:

fib n = second $ (0,1,1,1) ** n where
   p ** 0 = (1,0,0,1)
   p ** 1 = p
   p ** n | even n = (p `x` p) ** (n `div` 2)
          | otherwise = p `x` (p ** (n-1))
   (a,b,c,d) `x` (q,r,s,t) = (a*q+b*s, a*r+b*t,c*q+d*s,c*r+d*t)
   second (_,f,_,_) = f

(That was really fun to write, but I'm always grateful for suggestions)

Upvotes: 1

Antal Spector-Zabusky
Antal Spector-Zabusky

Reputation: 36622

A list comprehension is guaranteed to look at every element of the list. You want takeWhile :: (a -> Bool) -> [a] -> [a]. With it, your list is simply takeWhile (< 1000000) $ map fib [1..]. The takeWhile function simply returns the leading portion of the list which satisfies the given predicate; there's also a similar dropWhile function which drops the leading portion of the list which satisfies the given predicate, as well as span :: (a -> Bool) -> [a] -> ([a], [a]), which is just (takeWhile p xs, dropWhile p xs), and the similar break, which breaks the list in two when the predicate is true (and is equivalent to span (not . p). Thus, for instance:

  • takeWhile (< 3) [1,2,3,4,5,4,3,2,1] == [1,2]
  • dropWhile (< 3) [1,2,3,4,5,4,3,2,1] == [3,4,5,4,3,2,1]
  • span (< 3) [1,2,3,4,5,4,3,2,1] == ([1,2],[3,4,5,4,3,2,1])
  • break (> 3) [1,2,3,4,5,4,3,2,1] == ([1,2,3],[4,5,4,3,2,1])

Upvotes: 3

antonakos
antonakos

Reputation: 8361

The check fib x < 1000000 in the list comprehension filters away the fib x values that are less than 1000000; but the list comprehension has no way of knowing that greater values of x imply greater value of fib x and hence must continue until all x have been checked.

Use takeWhile instead:

takeWhile (< 1000000) [ fib x | x <- [0..35]]

Upvotes: 10

Bas Bossink
Bas Bossink

Reputation: 9678

The simplest thing I can think of is:

[ fib x | x <- [1..1000000] ]

Since fib n > n for all n > 3.

Upvotes: 0

Related Questions