#+Title: CS-3MI3 Homework 2 Sample Code
#+Author: Mark Armstrong, PhD Candidate, McMaster University
#+Date: September 20th, 2019
#+Description: Sample code to help with homework 2
#+Options: toc:nil num:nil
#+LaTeX_header: \usepackage{unicode}

This code is provided to help with concepts needed in homework 2.

* Learning from the literate portions of this file
:PROPERTIES:
:CUSTOM_ID: Learning-from-the-literate-portions-of-this-file
:END:

The literate portions of this document contain explanations
about /how/ to define/work with new types (or an existing type,
in the case of hashes) in Ruby and F#.

You may take this document as a guide for your literate writeups,
but usually, in your documents, you should instead discuss
implementation details (what and why) instead of explaining constructs
(how).

Some implementation details are discussed here in comments on the code.
So in your documents, you may wish to emulate
- the form of this document, by
- the content of the code comments.

* A custom type of lists
:PROPERTIES:
:CUSTOM_ID: A-custom-type-of-lists
:END:

Homework 2 asks you to build a type of trees using
- a class in Ruby, and
- an algebraic datatype in F#.

A similar, but slightly simpler task, would be to build
our own type of lists in each language.

** A custom type of lists in Ruby
:PROPERTIES:
:CUSTOM_ID: A-custom-type-of-lists-in-Ruby
:END:

Being primarily an object-oriented language,
in Ruby, we implement our own types as /classes/.

In this case, I will construct a class representing lists.
These lists are inductive; every list is either empty,
or an element (named ~here~) followed by a list (named ~next~).

Of course, since Ruby is dynamically typed,
it is up to me as the implementor to ensure
that the types of ~here~ and ~next~ are correct at all times.

# For the Org readers: the following code blocks are split up,
# to allow for literate portions between; this is accomplished
# by using ~noweb~ references, written as ~<<other-block-name>>~
# to chain them together.

To define a class, start with the keyword ~class~ followed by
a name for your new class.
#+name: MyList-header
#+begin_src ruby :results none
# My own class of lists.
# Note that these lists misbehave if you try to store nil in them;
# specifically, lists which start with nil are treated as empty,
# so everything following a nil in the list will be ignored.
class MyList
#+end_src

Ruby is a heavily dynamic language, and so usually the fields
(a.k.a., attributes, data, member variables)
of a class do not need to be declared.
However, it can be beneficial to declare them
using one of the keywords ~attr_reader~, ~attr_writer~ or ~attr_accessor~,
which create read, write and read/write methods automatically.
In the case of this custom list types, I want fields to be read-only,
so I make only readers for them.
#+name: MyList-fields
#+begin_src ruby :results none :noweb strip-export
<<MyList-header>>

  # Create readers for two fields, here and next.
  attr_reader :here
  attr_reader :next
#+end_src

If we want to perform some initialisation when creating an object
of this class (via the ~MyList.new~ method which is inherited from
the implicit super-class ~Class~ of ~MyList~),
you can define an ~initialize~ method to do so.
Note here that the local fields ~next~ and ~here~ are referred to
as ~@here~ and ~@next~ inside the class.
(Static fields, whose value would be shared by all objects,
would have their names prepended by ~@@~).
#+name: MyList-initialise
#+begin_src ruby :results none :noweb strip-export
<<MyList-fields>>

  # Initialise a list as a singleton or an empty list.
  def initialize(val=nil)
    @here = val
    @next = nil
    return self
  end
#+end_src

Our ~initialize~ method allows us to initiate lists as being
empty or singleton.
We now need some method to build up lists;
here, I define ~prepend~ to do so.
#+name: MyList-prepend
#+begin_src ruby :results none :noweb strip-export
<<MyList-initialise>>

  # Add a value to the beginning of a list
  # Note that we test if the head (@here) is tested against nil;
  # lists with a nil head are considered to be empty.
  def prepend(val)
    if @here != nil
      # Reproduce the current list, making it the new next list
      @next = self.clone()
    end
    @here = val
    return self
  end
#+end_src

For convenience, we also provide a method
to catenate lists.
We clone the list provided as argument
and make it the end of this list.
#+name: MyList-catenate
#+begin_src ruby :results none :noweb strip-export
<<MyList-prepend>>

  def catenate(l)
    if @here != nil and @next != nil
      # keep recursing until we reach the end of our list
      @next = @next.catenate(l)
    elsif @here != nil
      # at the end, attach a copy of l
      @next = l.clone()
    else
      # there is no list here; just copy l
      @here = l.here
      @next = l.next
    end
    return self
  end
#+end_src

We want our lists to be printable, so we override the ~to_s~
method to print their contents, rather than just
printing out an identifier for the object.
#+name: MyList-string
#+begin_src ruby :results none :noweb strip-export
<<MyList-catenate>>

  def to_s
    if @here and @next
      return @here.to_s + " :: " + @next.to_s
    elsif @here
      return @here.to_s + " :: eol"
    else
      return "eol"
    end
  end
#+end_src

Like any unit of code in Ruby,
class declarations end with ~end~.
#+name: MyList-end
#+begin_src ruby :results output :noweb strip-export
<<MyList-string>>

end
#+end_src

Now we can build a list and print it using the methods
defined above.
#+name: MyList-test
#+begin_src ruby :results output :noweb strip-export :tangle mylist.rb
<<MyList-end>>

# The list containing 1, prepended with 2, catenated with the list containing 3
# 2 ∷ 1 ∷ 3 ∷ eol
puts ((MyList.new(1)).prepend(2)).catenate(MyList.new(3))
#+end_src

#+RESULTS: MyList-test
: 2 :: 1 :: 3 :: eol

** A custom type of lists in F#
:PROPERTIES:
:CUSTOM_ID: A-custom-type-of-lists-in-F#
:END:

#+name: fs-module
#+begin_src fsharp :tangle mylist.fs
module SomeLists
#+end_src

In F#, we have /algebraic/ or /inductive/ datatypes
as the principal method for defining new types.

Since lists /are/ an inductive datatype, representing them
in this way is trivial.

A list is either empty or the catenation of an integer with a list.
#+name: fs-MyList
#+begin_src fsharp
type MyList = Empty | Cons of int * MyList
#+end_src

Then we can write lists as follows.
#+name: fs-some-lists
#+begin_src fsharp :noweb strip-export
<<fs-MyList>>

let singleton = Cons(1, Empty) // 1 ∷ []
let binary = Cons(2, singleton) // 2 ∷ 1 ∷ []
let ternary = Cons(1,Cons(2,Cons(3,Empty))) // 1 ∷ 2 ∷ 3 ∷ []
#+end_src

A nice advantage of algebraic datatypes is that they can be pretty-printed
without any additional effort; the output is simply
the sequence of constructors that make it up.
#+begin_src fsharp :noweb strip-export :results output :tangle mylist.fs
<<fs-some-lists>>

printfn "A singleton list: %O" singleton
printfn "A two-element list: %O" binary
printfn "A three-element list: %O" ternary
#+end_src

#+RESULTS:
: A singleton list: Cons (1,Empty)
: A two-element list: Cons (2,Cons (1,Empty))
: A three-element list: Cons (1,Cons (2,Cons (3,Empty)))

* The hash type in Ruby
:PROPERTIES:
:CUSTOM_ID: The-hash-type-in-Ruby
:END:

Homework 2 also asks you to convert your tree type to and from hashes.

Hashes, also called associative arrays, are another type of collection
available in many languages.
#+begin_src ruby :results output
list_like_hash = { 0 => "this", 1 => "that", 2 => "the other" }

puts list_like_hash
puts "#{list_like_hash[0]}, #{list_like_hash[1]} and the #{list_like_hash[2]}"
#+end_src

#+RESULTS:
: {0=>"this", 1=>"that", 2=>"the other"}
: this, that and the the other

Hashes in Ruby can be heterogeneous, storing elements of different types.
#+begin_src ruby :results output
heterogeneous_hash = {0 => 0, 1 => "uh... one?"}

puts heterogeneous_hash
#+end_src

#+RESULTS:
: {0=>0, 1=>"uh... one?"}

Note that lists are also heterogeneous in Ruby!
#+begin_src ruby :results output
heterogeneous_list = [0, "uh... one?"]

puts heterogeneous_list
#+end_src

#+RESULTS:
: 0
: uh... one?

The difference between hashes and lists are that lists
are indexed by numbers, starting from 0.
Hashes can be indexed by any type (and the types of keys can vary
for a single hash, too!).
Note that hashes also have the ~each~ method for looping over the contents.
#+begin_src ruby :results output
owing = {"Bob" => 200, "Larry" => -3, "Archibald" => 9001}

owing.each{ |p,a| puts "#{p} owes me #{a}" }
#+end_src

#+RESULTS:
: Bob owes me 200
: Larry owes me -3
: Archibald owes me 9001