! This program calculates the nth fibonacci number
! using alrogirhtm 1A: naive binary recursion
!
! compiled: n/a
! executed: hope -f f1a.hop n
! 
uses lists;

! naive binary recursion: F(n) = F(n-1) + F(n-2)
dec frec : num -> num;
--- frec 0 <= 0;
--- frec 1 <= 1;
--- frec(n+2) <= frec n + frec(n+1);

! negative argument handling: F(-n) = F(n)*(-1)^(n+1)
dec f : num -> num;
--- f n <= (if n<0 and n mod 2=0 then \(n)=>0-n else id) (frec (abs n));

! Function main prepares a string with nth Fibonacci number for output
dec main : num -> list char;
--- main n <= concat [num2str n, "th Fibonacci number is ", num2str(f n)];

!! Output
write (output argv)
 where output ==
     \(n) => if 1 = length n then [ main number ]
             else [ "Usage: f1a.hop <n>" ]
 where number == str2num (argv @ 0);

! This program calculates the nth fibonacci number
! using alrogirhtm 1B: cached binary recursion
!
! compiled: n/a
! executed: hope -f f1b.hop n
! 
uses lists;
! Hope does not come with a large precision integer library,
! so I had to implement a simple one.
type bignum == list num;
dec B : num;
--- B <= 1000000000000000;
! conversion from a regular number
dec fromnum : num -> bignum;
--- fromnum 0 <= [];
--- fromnum n <= n mod B :: fromnum(n div B);

! addition
dec bigadd : bignum # bignum -> bignum;
--- bigadd ([],n) <= n;
--- bigadd (n,[]) <= n;
--- bigadd (x::xs,y::ys) <= digit :: bigadd(carry, bigadd(xs, ys))
           where digit,carry == (sum mod B, if sum>=B then [sum div B] else [])
           where sum == x+y;

! Conversion of a big number to a string
! empty list is the literal zero
! non-empty list is reversed (to place the most significant digit first),
! then the first digit is converted to string via num2str, while other
! digits are converted and padded with zeroes on the left to be as long
! as the string representation of B-1.
dec pad : char # num # list char -> list char;
--- pad (c, n, x) <= if length(x) = n then x
                     else pad(c,n,c::x);
dec bignum2str : bignum -> list char;
--- bignum2str [] <= "0";
--- bignum2str x <= num2str y <> concat (map pn2s ys)
    where (y::ys) == reverse x
    where pn2s == ! padded num2str
     \(n) => pad ('0', length (num2str (B-1)), num2str n);

! Conversion of a big signed number to a string
type sbignum == bool # bignum;
dec sbignum2str : sbignum -> list char;
--- sbignum2str (false, x) <= bignum2str x;
--- sbignum2str (true, x) <= "-" <> bignum2str x;

! All done with the big number library, now the actual Fibonacci program:

! function mfib performs binary recursion but it passes along a list of known 
! calculated numbers. If the value is in the list, it is returned immediately.
dec mfib : num -> list bignum -> bignum # list bignum;
--- mfib n l <= if length l > n then (l@n, l)
                else (sum, l2<>[sum])
                where sum == bigadd(p1, p2)
                where (p1,l2) ==  mfib (n-1) l1
                where (p2,l1) ==  mfib (n-2) l;

dec fib : num -> bignum;
--- fib n <= a where (a,_) == mfib n l
               where l == [fromnum 0, fromnum 1];

! function f takes care of negative arguments and returns the list member
dec f : num -> sbignum;
--- f n <= (n<0 and n mod 2=0, fib(abs n));

! Function main prepares a string with nth Fibonacci number for output
dec main : num -> list char;
--- main n <= concat [num2str n, "th Fibonacci number is ", sbignum2str(f n)];

! Output
write (output argv)
 where output ==
     \(n) => if 1 = length n then [ main number ]
             else [ "Usage: f1a.hop <n>" ]
 where number == str2num (argv @ 0);

! This program calculates the nth fibonacci number
! using alrogirhtm 2A: cached linear recursion (as lazy infinite list)
!
! compiled: n/a
! executed: hope -f f2a.hop n
!
uses lists;
! Hope does not come with a large precision integer library,
! so I had to implement a simple one.
type bignum == list num;
dec B : num;
--- B <= 1000000000000000;
! conversion from a regular number
dec fromnum : num -> bignum;
--- fromnum 0 <= [];
--- fromnum n <= n mod B :: fromnum(n div B);

! addition
dec bigadd : bignum # bignum -> bignum;
--- bigadd ([],n) <= n;
--- bigadd (n,[]) <= n;
--- bigadd (x::xs,y::ys) <= digit :: bigadd(carry, bigadd(xs, ys))
           where digit,carry == (sum mod B, if sum>=B then [sum div B] else [])
           where sum == x+y;

! Conversion of a big number to a string
! empty list is the literal zero
! non-empty list is reversed (to place the most significant digit first),
! then the first digit is converted to string via num2str, while other
! digits are converted and padded with zeroes on the left to be as long
! as the string representation of B-1.
dec pad : char # num # list char -> list char;
--- pad (c, n, x) <= if length(x) = n then x
                     else pad(c,n,c::x);
dec bignum2str : bignum -> list char;
--- bignum2str [] <= "0";
--- bignum2str x <= num2str y <> concat (map pn2s ys)
    where (y::ys) == reverse x
    where pn2s == ! padded num2str
     \(n) => pad ('0', length (num2str (B-1)), num2str n);

! Conversion of a big signed number to a string
type sbignum == bool # bignum;
dec sbignum2str : sbignum -> list char;
--- sbignum2str (false, x) <= bignum2str x;
--- sbignum2str (true, x) <= "-" <> bignum2str x;

! All done with the big number library, now the actual Fibonacci program:

! Infinite list fibs contains all Fibonacci numbers, using the usual,
! for lazy languages, approach of: 0 cons 1 cons zipwith + self (tail self)
dec fibs : list bignum;
--- fibs <= fs whererec fs == fromnum 0::fromnum 1::map bigadd (fs||tail fs);

! function f takes care of negative arguments and returns the list member
dec f : num -> sbignum;
--- f n <= (n<0 and n mod 2=0, fibs@(abs n));

! Function main prepares a string with nth Fibonacci number for output
dec main : num -> list char;
--- main n <= concat [num2str n, "th Fibonacci number is ", sbignum2str(f n)];
! Output
write (output argv)
 where output ==
     \(n) => if 1 = length n then [ main number ]
             else [ "Usage: f2a.hop <n>" ]
 where number == str2num (argv @ 0);

! This program calculates the nth fibonacci number
! using alrogirhtm 2B: linear recursion with accumulator
!
! compiled: n/a
! executed: hope -f f2b.hop n
!
uses lists;
! Hope does not come with a large precision integer library,
! so I had to implement a simple one.
type bignum == list num;
dec B : num;
--- B <= 1000000000000000;
! conversion from a regular number
dec fromnum : num -> bignum;
--- fromnum 0 <= [];
--- fromnum n <= n mod B :: fromnum(n div B);

! addition
dec bigadd : bignum # bignum -> bignum;
--- bigadd ([],n) <= n;
--- bigadd (n,[]) <= n;
--- bigadd (x::xs,y::ys) <= digit :: bigadd(carry, bigadd(xs, ys))
           where digit,carry == (sum mod B, if sum>=B then [sum div B] else [])
           where sum == x+y;

! Conversion of a big number to a string
! empty list is the literal zero
! non-empty list is reversed (to place the most significant digit first),
! then the first digit is converted to string via num2str, while other
! digits are converted and padded with zeroes on the left to be as long
! as the string representation of B-1.
dec pad : char # num # list char -> list char;
--- pad (c, n, x) <= if length(x) = n then x
                     else pad(c,n,c::x);
dec bignum2str : bignum -> list char;
--- bignum2str [] <= "0";
--- bignum2str x <= num2str y <> concat (map pn2s ys)
    where (y::ys) == reverse x
    where pn2s == ! padded num2str
     \(n) => pad ('0', length (num2str (B-1)), num2str n);

! Conversion of a big signed number to a string
type sbignum == bool # bignum;
dec sbignum2str : sbignum -> list char;
--- sbignum2str (false, x) <= bignum2str x;
--- sbignum2str (true, x) <= "-" <> bignum2str x;

! All done with the big number library, now the actual Fibonacci program:

! Now, function fib, starting with 1 and 0, add the accumulator arguments,
! swap them, and recurse.
dec fib : num -> bignum;
--- fib n <= l (fromnum 1, fromnum 0, n)
    whererec l == \(a,b,succ c) => if c<1 then a else l(bigadd(a,b),a,c)
                  |(a,b,0) => fromnum 0;

! function f takes care of negative arguments and returns the list member
dec f : num -> sbignum;
--- f n <= (n<0 and n mod 2=0, fib(abs n));

! Function main prepares a string with nth Fibonacci number for output
dec main : num -> list char;
--- main n <= concat [num2str n, "th Fibonacci number is ", sbignum2str(f n)];
! Output
write (output argv)
 where output ==
     \(n) => if 1 = length n then [ main number ]
             else [ "Usage: f2b.hop <n>" ]
 where number == str2num (argv @ 0);

Hope does not support non-recursive loops.
Rewriting this algorithm using recursion gives ALGORITHM 2B.

! This program calculates the nth fibonacci number
! using alrogirhtm 3A: matrix multiplication
!
! compiled: n/a
! executed: hope -f f3a.hop n
!
uses lists;

! Hope does not come with a large precision integer library,
! so I had to implement a simple one.
type bignum == list num;
dec B : num;
--- B <= 1000000000000000;
! conversion from a regular number
dec fromnum : num -> bignum;
--- fromnum 0 <= [];
--- fromnum n <= n mod B :: fromnum(n div B);

! addition
dec bigadd : bignum # bignum -> bignum;
--- bigadd ([],n) <= n;
--- bigadd (n,[]) <= n;
--- bigadd (x::xs,y::ys) <= digit :: bigadd(carry, bigadd(xs, ys))
           where digit,carry == (sum mod B, if sum>=B then [sum div B] else [])
           where sum == x+y;

! Conversion of a big number to a string
! empty list is the literal zero
! non-empty list is reversed (to place the most significant digit first),
! then the first digit is converted to string via num2str, while other
! digits are converted and padded with zeroes on the left to be as long
! as the string representation of B-1.
dec pad : char # num # list char -> list char;
--- pad (c, n, x) <= if length(x) = n then x
                     else pad(c,n,c::x);
dec bignum2str : bignum -> list char;
--- bignum2str [] <= "0";
--- bignum2str x <= num2str y <> concat (map pn2s ys)
    where (y::ys) == reverse x
    where pn2s == ! padded num2str
     \(n) => pad ('0', length (num2str (B-1)), num2str n);

! Conversion of a big signed number to a string
type sbignum == bool # bignum;
dec sbignum2str : sbignum -> list char;
--- sbignum2str (false, x) <= bignum2str x;
--- sbignum2str (true, x) <= "-" <> bignum2str x;

dec halve : bignum -> bignum;
--- halve n <= reverse (l(reverse n,false))
whererec l == \((x1::(x2::xs)),c) => (if h>0 or c then [h] else [])
                                  <> l((x2+x1 mod 2*B)::xs,true)
                                  where h == x1 div 2
              |([],_) => []
              |([x],_) => [x div 2];

dec bigeven : bignum -> bool;
--- bigeven [] <= true;
--- bigeven (x::xs) <= x mod 2=0;

! multiplication by repeated addition
dec bigmul : bignum # bignum -> bignum;
--- bigmul (b,n) <= l(fromnum 0,b,n)
whererec l == \(u,b,[]) => u
              |(u,b,[0]) => u
              |(u,b,n) => if bigeven n then l(u,bigadd(b,b),halve n)
                                       else l(bigadd(u,b),bigadd(b,b),halve n);

! All done with the big number library, now the actual Fibonacci program:

! matrix transposition
dec transpose : list (list alpha) -> list (list alpha);
--- transpose ([]::_) <= [];
--- transpose n <= map head n :: transpose (map tail n);

! bignum dot product
dec dot : list bignum -> list bignum -> bignum;
--- dot a b <= foldr (fromnum 0, bigadd) (map bigmul (a||b));

! matrix multiplication
dec mm : list (list bignum) # list (list bignum) -> list (list bignum);
--- mm (a,b) <= map (\(row) => map (\(col) => dot row col) tb) a
                where tb == transpose b;

! exponentiation by repeated squaring
! Takes object b and unity u, and raises to nth power using multiplication f
dec power : (alpha # alpha -> alpha) -> alpha -> alpha -> num -> alpha;
--- power f u b 0 <= u;
--- power f u b n <= if n mod 2=0 then power f     u    (f(b,b)) (n div 2)
                                  else power f (f(u,b)) (f(b,b)) (n div 2);

! Function fib raises the matrix [1 1][1 0] to n-1'st power
dec fib : num -> bignum;
--- fib 0 <= fromnum 0;
--- fib (n+1) <= let [[a,_],_] == power mm u t n
                 where t,u == ([[fromnum 1,fromnum 1],[fromnum 1,fromnum 0]],
                               [[fromnum 1,fromnum 0],[fromnum 0,fromnum 1]])
                 in a;

! function f takes care of negative arguments and calls fib
dec f : num -> sbignum;
--- f n <= (n<0 and n mod 2=0, fib(abs n));

! Function main prepares a string with nth Fibonacci number for output
dec main : num -> list char;
--- main n <= concat [num2str n, "th Fibonacci number is ", sbignum2str(f n)];
! Output
write (output argv)
 where output ==
     \(n) => if 1 = length n then [ main number ]
             else [ "Usage: f3a.hop <n>" ]
 where number == str2num (argv @ 0);

! This program calculates the nth fibonacci number
! using alrogirhtm 3B: fast recursion
!
! compiled: n/a
! executed: hope -f f3b.hop n
!
uses lists;
! Hope does not come with a large precision integer library,
! so I had to implement a simple one.
type bignum == list num;
dec B : num;
--- B <= 1000000000000000;
! conversion from a regular number
dec fromnum : num -> bignum;
--- fromnum 0 <= [];
--- fromnum n <= n mod B :: fromnum(n div B);

! addition
dec bigadd : bignum # bignum -> bignum;
--- bigadd ([],n) <= n;
--- bigadd (n,[]) <= n;
--- bigadd (x::xs,y::ys) <= digit :: bigadd(carry, bigadd(xs, ys))
           where digit,carry == (sum mod B, if sum>=B then [sum div B] else [])
           where sum == x+y;

! Conversion of a big number to a string
! empty list is the literal zero
! non-empty list is reversed (to place the most significant digit first),
! then the first digit is converted to string via num2str, while other
! digits are converted and padded with zeroes on the left to be as long
! as the string representation of B-1.
dec pad : char # num # list char -> list char;
--- pad (c, n, x) <= if length(x) = n then x
                     else pad(c,n,c::x);
dec bignum2str : bignum -> list char;
--- bignum2str [] <= "0";
--- bignum2str x <= num2str y <> concat (map pn2s ys)
    where (y::ys) == reverse x
    where pn2s == ! padded num2str
     \(n) => pad ('0', length (num2str (B-1)), num2str n);

! Conversion of a big signed number to a string
type sbignum == bool # bignum;
dec sbignum2str : sbignum -> list char;
--- sbignum2str (false, x) <= bignum2str x;
--- sbignum2str (true, x) <= "-" <> bignum2str x;

dec halve : bignum -> bignum;
--- halve n <= reverse (l(reverse n,false))
whererec l == \((x1::(x2::xs)),c) => (if h>0 or c then [h] else [])
                                  <> l((x2+x1 mod 2*B)::xs,true)
                                  where h == x1 div 2
              |([],_) => []
              |([x],_) => [x div 2];

dec bigeven : bignum -> bool;
--- bigeven [] <= true;
--- bigeven (x::xs) <= x mod 2=0;

! multiplication by repeated addition
dec bigmul : bignum # bignum -> bignum;
--- bigmul (b,n) <= l(fromnum 0,b,n)
whererec l == \(u,b,[]) => u
              |(u,b,[0]) => u
              |(u,b,n) => if bigeven n then l(u,bigadd(b,b),halve n)
                                       else l(bigadd(u,b),bigadd(b,b),halve n);

! All done with the big number library, now the actual Fibonacci program:

! Function fib calculates a pair of fibonacci numbers according to
! the recurrent relationship: 
! F(2n-1) = F(n-1)^2 + F(n)^2
! F(2n) = (2F(n-1) + F(n))F(n)
!
! in this function, k1 = F(n-1), k2 = F(n), k3 = F(n+1)
dec fib : num -> bignum;
--- fib n <= a where (a,b) == l(n)
    whererec l == \(n) =>
        if n<1 then (fromnum 0,fromnum 0) else
        if n=1 then (fromnum 1,fromnum 0) else
        if n mod 2 = 0 then
            (bigmul(k2,bigadd(k1,k3)), bigadd(k1s,k2s))
        else
            (bigadd(k3s,k2s), bigmul(k2,bigadd(k1,k3)))
        where k3  == bigadd(k2,k1)
        where k2s == bigmul(k2,k2)
        where k1s == bigmul(k1,k1)
        where k3s == bigmul(bigadd(k2,k1),bigadd(k2,k1))
        where (k2,k1) == l(n div 2);

! function f takes care of negative arguments and calls fib
dec f : num -> sbignum;
--- f n <= (n<0 and n mod 2=0, fib(abs n));

! Function main prepares a string with nth Fibonacci number for output
dec main : num -> list char;
--- main n <= concat [num2str n, "th Fibonacci number is ", sbignum2str(f n)];
! Output
write (output argv)
 where output ==
     \(n) => if 1 = length n then [ main number ]
             else [ "Usage: f3b.hop <n>" ]
 where number == str2num (argv @ 0);

! This program calculates the nth fibonacci number
! using alrogirhtm 3C: Binet formula with rounding
!
! compiled: n/a
! executed: hope -f f3c.hop n
!
uses lists;

! Hope does not come with a large precision floating-point library
! the largest correct number on my system is F(70)

! Function fib calculates the fibonacci number
! as the closest integer to phi^n/sqrt(5)
dec fib : num -> num;
--- fib n <= floor (0.5 + pow(phi,n)/sqrt(5) )
           where phi == (1+sqrt(5))/2;

! function f takes care of negative arguments and calls fib
dec f : num -> num;
--- f n <= (if n<0 and n mod 2=0 then \(n)=>0-n else id) (fib (abs n));

! Function main prepares a string with nth Fibonacci number for output
dec main : num -> list char;
--- main n <= concat [num2str n, "th Fibonacci number is ", num2str(f n)];
! Output
write (output argv)
 where output ==
     \(n) => if 1 = length n then [ main number ]
             else [ "Usage: f3c.hop <n>" ]
 where number == str2num (argv @ 0);