7 Replies - 957 Views - Last Post: 15 August 2016 - 09:13 AM

#1 O'Niel  Icon User is offline

  • D.I.C Regular

Reputation: 14
  • View blog
  • Posts: 389
  • Joined: 13-September 15

Fibonacci in Haskell

Posted 14 August 2016 - 10:23 AM

Hi

I tried to make a function in Haskell which calculates the Fibonacci-sequence. The Fibonacci-algorithm worked, but then I tried to add a recursive function so I could output a longer sequence and not just one number.

Code:
--Fibonacci

--The Fibonacci algorithm
fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib x = fib(x-1) + fib(x-2)

--Recursive loop to repeat the fib-function multiple times
repeatFib 0 = 0
repeatFib x =
    putStrLn $ show $ fib x
    repeatFib (x - 1)

main =
    repeatFib 10




Error:

Quote

haskell_test.hs:12:23:
Couldn't match expected type `(Int -> IO ()) -> Int -> String'
with actual type `Int'
The function `fib' is applied to three arguments,
but its type `Int -> Int' has only one
In the second argument of `($)', namely `fib x repeatFib (x - 1)'
In the second argument of `($)', namely
`read $ fib x repeatFib (x - 1)'


I don't really understand the error, but I guess that the fib-function also takes the words on line 13 as an argument...
What am I doing wrong?

Thanks!

Is This A Good Question/Topic? 0
  • +

Replies To: Fibonacci in Haskell

#2 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2517
  • View blog
  • Posts: 4,001
  • Joined: 21-June 11

Re: Fibonacci in Haskell

Posted 14 August 2016 - 10:51 AM

Outside of do-notation a line break in an expression has no special meaning, so:

putStrLn $ show $ fib x
repeatFib (x - 1)


is the same as

putStrLn $ show $ fib x repeatFib (x - 1)


So fib is called with three arguments instead of one. To get the behavior you want, use do notation or >>.

Another problem is that your two cases produce different types. repeatFib 0 = 0 produces a number, but your other case produces an IO action. Both cases need to produce the same type, so the base case should be repeatFib 0 = return ().
Was This Post Helpful? 1
  • +
  • -

#3 O'Niel  Icon User is offline

  • D.I.C Regular

Reputation: 14
  • View blog
  • Posts: 389
  • Joined: 13-September 15

Re: Fibonacci in Haskell

Posted 14 August 2016 - 03:16 PM

Thanks!

Working code:
--Fibonacci

--The Fibonacci algorithm
fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib x = fib(x-1) + fib(x-2)

--Recursive loop to repeat the fib-function multiple times
x = 0
repeatFib x y = do
    putStrLn $ show $ fib x
    if x == y
        then return ()
    else repeatFib (x + 1) y

main =
    repeatFib 0 100



(I edited my code a bit so you can choose how much numbers you want).

Do I need return () because the return-function (not keyword like in imperative languages) gives back a monad, and Haskell uses monads for IO? So IO and Return are both Monads and thus from the same type?

This post has been edited by O'Niel: 14 August 2016 - 03:16 PM

Was This Post Helpful? 0
  • +
  • -

#4 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2517
  • View blog
  • Posts: 4,001
  • Joined: 21-June 11

Re: Fibonacci in Haskell

Posted 14 August 2016 - 07:06 PM

Note that your definition of x on line 10 serves no purpose and is never used.

View PostO, on 15 August 2016 - 12:16 AM, said:

Do I need return () because the return-function (not keyword like in imperative languages) gives back a monad, and Haskell uses monads for IO? So IO and Return are both Monads and thus from the same type?


Yes, kind of. Return "wraps" a given value in a monad of your choosing. So since IO is a monad, you can use return to get an IO value.
Was This Post Helpful? 1
  • +
  • -

#5 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon


Reputation: 6995
  • View blog
  • Posts: 14,628
  • Joined: 16-October 07

Re: Fibonacci in Haskell

Posted 15 August 2016 - 04:17 AM

As a side note, in Haskell you'd do well to think along the lines of avoiding IO until the last possible minute.

Also, mapping. Mapping damn near everything, really.

For instance, given your code, you can easily make a series by simply doing:
*Main> map fib [1..10]
[1,1,2,3,5,8,13,21,34,55]



Of course, to print them, you wanted to apply show:
*Main> map show $ map fib [1..10]
["1","1","2","3","5","8","13","21","34","55"]



This can also be written as:
*Main> map ( show . fib ) [1..10]
["1","1","2","3","5","8","13","21","34","55"]


Here, the result of show . fib is a composite of the two, taking an Int and splitting out a string. This one function is then mapped to the series.

It would be nice if you could use the same logic with putStrLn. You can't, exactly. But, there are some helper functions out there. For the purposes of printing, all you need know is that this works:
*Main> mapM_ putStrLn $ map ( show . fib ) [1..10]
1
1
2
3
5
8
13
21
34
55




One reason to prefer a mapping is Haskell's wonderful lazy infinite series handling. i.e., this is valid, if silly:
mapM_ putStrLn $ map ( show . fib ) [0..]



Hmm... just to see where we're at:
mapM_ putStrLn $ map (\i ->(show i) ++ " : " ++ (show $ fib i)) [0..]



Hope this helps.
Was This Post Helpful? 1
  • +
  • -

#6 O'Niel  Icon User is offline

  • D.I.C Regular

Reputation: 14
  • View blog
  • Posts: 389
  • Joined: 13-September 15

Re: Fibonacci in Haskell

Posted 15 August 2016 - 06:45 AM

Thanks! So actually by using mapping I don't need the recursion function anymore?
Was This Post Helpful? 0
  • +
  • -

#7 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2517
  • View blog
  • Posts: 4,001
  • Joined: 21-June 11

Re: Fibonacci in Haskell

Posted 15 August 2016 - 09:09 AM

No, when using map, you don't need to use recursion yourself. map is already recursive. It's definition looks something like this:

map _ [] = []
map f (x:xs) = f x : map f xs


So the logic of how to iterate the list is already in there. You just need to tell it what to do with each element.
Was This Post Helpful? 1
  • +
  • -

#8 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon


Reputation: 6995
  • View blog
  • Posts: 14,628
  • Joined: 16-October 07

Re: Fibonacci in Haskell

Posted 15 August 2016 - 09:13 AM

For this, no. Haskell is a good place to use recursion, as it does it well. Your fib is a classic example of recursive goodness.

However, if you have a series, a list, there are just so many canned tools that rolling your own recursion is a rare case. To transform, you map. If you need to consider all the elements in a list, you fold. If you want only some, you filter, skip, take, split, whatever, fold.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1