Fibonacci number: support negative values, recursive and optimized versions

fib.hs

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

fib2 :: Integer -> Integer
fib2 n = fib2' 0 1 2 n

fib2' :: Integer -> Integer -> Integer -> Integer -> Integer
fib2' a b i n
  | i > (abs n) = if n == 0 then a else b
  | n >= 0 = fib2' b (a + b) (i + 1) n
  | otherwise = fib2' b (a - b) (i + 1) n

fib.js

function f1(n) {
  if (n === 0) return 0
  if (Math.abs(n) === 1) return 1
  if (n >= 0) return f1(n - 1) + f1(n - 2)
  return f1(n + 2) - f1(n + 1)
}

function f2(n) {
  const arr = [0, 1]
  const e = n < 0 ? -1 : 1
  const m = Math.abs(n)
  for (let i = 2; i <= m; i++)
    arr.push(arr[i - 2] + e * arr[i - 1])
  return arr[m]
}

f1(36) //?.$ 14930352 3068.251ms
f2(1476) //?.$ 1.3069892237633987e+308 0.392ms

JS version profiled with Quokka.js 👆

Haskell version profiled with :set +s in GHCi only:

fib 36 -- (45.70 secs, 15,587,214,080 bytes)
fib2 1476 -- (0.02 secs, 1,022,344 bytes)