Appendix A  Miscellaneous Examples

fib3 n =
  if n <= 1 then 1
  else
    if 2*k == n then ab*ab + b*b
    else ab*ab + 2*b*ab
    where k = n ‘div‘ 2
          (a,b) = aux k
          ab = a + b
          aux 0 = (1,0)
          aux 1 = (0,1)
          aux n =
            if 2*k == n then (aa+bb, ab2bb)
            else (ab2bb, ab2bb+aa+bb)
            where k = n ‘div‘ 2
                  (a,b) = aux k
                  aa = a*a
                  bb = b*b
                  ab2 = 2*a*b
                  ab2bb = ab2+bb