#!/usr/bin/perl

# types are indicated "in the rough" by $, @, %, &


# n! function

my $x = 1;
my $y = "x is $x";

print "$y\n";

# arrays

my @A = (2,4,6,8);

print $A[2], "\n";  # 6
# can also use as list

@A = (0,@A);  # cons

foreach $x (@A) {print "$x--";}
print @A+1;  # interprets @A to mean the length of A

my %hash;

sub factorial
{
   # parameters are in array @_
   my $n = $_[0]; # also my $n = shift;
   if ($n<2) {1} else {$n * factorial($n-1)} 
}

print "\nfact(6) is ", factorial(6), "\n";

# function to see if certain element is in a list
sub member
{
    my ($x,@L) = @_;  # head is element we want to look for
    my $answer = 0;   # initially answer is false
    foreach my $y (@L) 
    {
	if ($y == $x) {$answer = 1;}
    }
    $answer;
}



# pointers

my $x = 3;
my $px = \$x;  

print "value of px is $px\n";
print "value of px dereferenced is $$px\n";


# use pointers uniformly

my $gcd;  # Euclid's algorithm as a pointer to a function

$gcd =    sub {
                my ($a,$b) = @_;
                if ($a==0) {$b} else {$gcd->($b%$a,$a)}
              };

print $gcd->(12,8), "\n";


# K = lambda x. lambda y. x

$K = sub { my $x = $_[0]; sub { $x } };


# binary trees in perl
# we build tree nodes as objects (closures)

sub node
{
    my ($h,$l,$r) = @_;
    # return a hash table as an interface
     {
       head => $h,
       left => $l,
       right => $r
     }
} # node

# let "" represent the empty node

my $tree = node(5,node(3,"",node(4,"","")),node(9,"",""));

# $tree->{left}->{head} += 10;
print $tree->{left}->{head}, "\n";

sub preorder
{
    if ($_[0]!="") 
     { my $tree = $_[0];
       print $tree->{head}, " ";
       preorder($tree->{left});
       preorder($tree->{right})
     }
}

preorder($tree); print "\n";

# what's the difference between using a hash table instead of an interface
# function.  The difference is that everything becomes PUBLIC, with both
# read and write access from outside.  We can grant read-only access with

# { head => sub {head},
#   ...

# That is, let the entries of the hashtable be subroutines, which must
# be called to return a value.



# ---------------------  Perl Drills.  $%&\*@!  ------------------------

#0. Euclid's algorithm for computing the gcd of two numbers can be
#   written in Scheme as
#   (define (gcd a b) (if (= a 0) b (gcd (remainder b a) a)))
#   
#   Write it in Perl twice, one recursively and one using a while loop.
#   Try to use Perl's unique features.  For example, in the while
#   loop version, you shouldn't have to use any temporary variables.
#   There's a very similar function in my tutorial that will provide
#   you with a hint as to what I mean.  "remainder" is just %, like
#   in C/Java.

#1. define a function "doubles," that , given a list L, will return
#   a list with every element in L repeated, e.g:
#   doubles(1,2,3) should return (1,1,2,2,3,3).  You don't have to
#   do this recursively.  You can use "push".  The empty list is just ().

# -------------------  More Interesting Perl  -------------------------

#2. Write the following Scheme closure-function in Perl:
#
#   (define (makecounter)
#       (let ((x 0)) (lambda () (begin (set! x (+ x 1)) x))))
#
#   You need to understand the last section of the tutorial, and read
#   the "bank accounts in perl" example.  Note that you cannot use
#   a global variable for x since makecounter must be able to create
#   different "instances" of the counter function, each with its own'
#   local x to count up from.
#
#   After you've written the function and tested it, take a moment
#   to be proud of yourself, then change the word "my" in your program
#   to "local", and observe what happens.  What comments have you?


#  The rest of the assignment can be completed with EITHER SCHEME OR PERL.
#  Do the exercises from the handout "Modularity, Objects, and State",
#  numbers 3.1-3.4 (3.5 on page 179 is optional).


#3. Using the formulation of trees above, write a function to insert a
#   number into a binary search tree.

# destructive insert. - changes structure of tree.
sub insert
{
    my ($x,$tree) = @_;
    if ($tree=="") {node($x,"","")}
    else
    {
	if ($tree->{head} > $x) # go left
	{ $tree->{left} = insert($x,$tree->{left}); }
        else
	{ $tree->{right} = insert($x,$tree->{right}); }
	$tree   # Original root node still valid
    }
}


$tree = insert(11,$tree);
preorder($tree); print "\n";


print "\ndone\n";

#3b. Using the formulation of trees above, write a function to return the
#    smallest number is a tree of numbers (the tree is not necessarily a bst)

