Рассмотрим лобовое решение с бинарной рекурсией:

fib :: Int -> Int
-- fib :: Integer -> Integer избыточно, так как не достигнем
fib 1 = 1
fib 2 = 1
fib n = fib (n-1) + fib (n-2)

тогда сам список чисел Фиббоначи может быть задан следующим образом:

fibset = [ fib n | n <- [1..] ]

Однако данный способ вычисления является хоть и простым, но крайне затратным, так как вынужден делать бинарное дерево ветвлений вычислений при рекурсивном спуске. При этом хотя все вычисления одинаковые, но они делаются независимо и вынуждены занимать всю доступную память. Таким образом, на некоторых компьютерах вычислить даже 40-й элементы последовательности является проблематичным, а 45-й, тем более 50-й вычислить нереально практически на всех доступных персональных компьютерах.

Согласно сайту cubbi.com: fibonacci numbers in haskell возможно улучшить даже бинарную рекурсию мемоизацией (кэшированием) промежуточных результатов:

import Data.MemoTrie
 
-- Naive binary recursion: F(n) = F(n-1) + F(n-2) with 
-- using memotrie from http://haskell.org/haskellwiki/MemoTrie
fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = mfib (n-2) + mfib (n-1) where mfib = memo fib

(Эксперименты показывают, что вычисления с мемоизацией не ускоряют бинарную рекурсию, лавиноообразное число вызовов с ростом n становится слишком велико).

Рассмотрим императивное решение с циклом на Паскале:

program fibb;
var
  f1,f2,f3: Int64;
  n,i: integer;
begin
f1:=1; f2:=1;
write ('please, input n='); read(n);
for i:=1 to (n-2) do 
begin
 f3 := f2 + f1;  f1 := f2;  f2 := f3
end;
writeln ('f=', f3);
end.

Эта программа позволяет быстро вычислять до 92-го члена последовательности (дальше возникают проблемы с превышением числового диапазона Int64).

Сделаем аналог его, но уже с рекурсией вместо цикла. Рекурсия получится линейной, и добавится новый параметр «аккумулятор»:

f a b 0 = b
f a b n = f b (a+b) (n-1)
fib n = f 1 1 n

запуск осуществляется так:

fib n

Этот вариант уже не имеет проблемных мест и позволяет вычислять даже 100000-й элемент последовательности за 0.5-1.5 минуты на ноутбуке.

Другой вариант из сайта The Fibonacci sequence с аккумулятором и хвостовой рекурсией (используя расширения языка):

{-# LANGUAGE BangPatterns #-}
fib n = go n (0,1)
  where
    go !n (!a, !b) | n==0      = a
                   | otherwise = go (n-1) (b, a+b)

Вот императивный вариант с монадой состояния (оттуда же):

import Control.Monad.State
fib n = flip evalState (0,1) $ do
  forM [0..(n-1)] $ \_ -> do
    (a,b) <- get
    put (b,a+b)
  (a,b) <- get
  return a

А статья Мягкое введение в Haskell-1 предлагает решение в виде циклического бесконечного списка:

fib = 1 : 1 : [ a+b | (a,b) <- zip fib (tail fib) ]