use context essentials2021

# CMPU 101, Section 52
# 20 Feb 2023

import math as M


#
# Warm-up
#

fun add-prev(lst :: List<Number>) -> List<Number>:
  doc: "Make a list where each number is the number in the original list plus the previous number in the original list"

  fun add-prev-helper(l :: List<Number>, prev :: Number) -> List<Number>:
    doc: "Make a list where prev is added to the first number, which is then added to the next number, and so on"
    cases (List) l:
      | empty => empty
      | link(f, r) => link(f + prev, add-prev-helper(r, f))
    end
  end

  add-prev-helper(lst, 0)

where:
  add-prev([list: ]) is [list: ]
  add-prev([list: 1]) is [list: 1]
  add-prev([list: 1, 2]) is [list: 1, 3]
  add-prev([list: 1, 2, 3]) is [list: 1, 3, 5]
end

########################################################

#
# Fun with flags
#

austria = [list: "red", "white", "red"]
germany = [list: "black", "red", "yellow"]
yemen = [list: "red", "white", "black"]

#
# Version 1: Only works right for three stripes:
#

"*******************************************************"
"Version 1:"


fun striped-flag-v1(colors :: List<String>) -> Image:
  doc: "Produce a flag with horizontal stripes"
  cases (List) colors:
    | empty => empty-image
    | link(color, rest) =>
      stripe = rectangle(120, 30, "solid", color)
      above(stripe, striped-flag-v1(rest))
  end
end

countries = [list: austria, germany, yemen]

"Flags with 3 stripes: Austria, Germany, Yemen"
map(striped-flag-v1, countries)


ukraine = [list: "blue", "yellow"]

# "Ukrainian flag (2 stripes):"
# striped-flag-v1(ukraine)

# Wrong dimensions!



FLAG-WIDTH = 120
FLAG-HEIGHT = 90


# Bad first attempt:

"*******************************************************"
"Version 2:"

#|
fun striped-flag-v2(colors :: List<String>) -> Image:
  doc: "Produce a flag with horizontal stripes"
  
  cases (List) colors:
    | empty => empty-image
    | link(color, rest) =>
      height = FLAG-HEIGHT / length(colors)
      stripe = rectangle(FLAG-WIDTH, height, "solid", color)
      above(stripe, striped-flag-v2(rest))
  end
end

"Flags of Germany and Ukraine (3 and 2 stripes):"
map(striped-flag-v2, [list: germany, ukraine])
|#

"*******************************************************"
"Version 3:"

#|
# Working: We need to compute the height of each stripe before we do the recursion

fun striped-flag-v3(colors :: List<String>) -> Image:
  doc: "Produce a flag with horizontal stripes"
  
  height = FLAG-HEIGHT / length(colors)
  
  fun stripe-helper(lst :: List<String>) -> Image:
    cases (List) lst:
      | empty => empty-image
      | link(color, rest) =>
        stripe = rectangle(FLAG-WIDTH, height, "solid", color)
        above(stripe, stripe-helper(rest))
    end
  end
  
  stripe-helper(colors)
end

map(striped-flag-v3, [list: germany, ukraine])
|#

#
# Further recursion
#


fun alternating(lst :: List<Number>) -> List<Number>:
  doc: "Select every other element of the list"
  cases (List) lst:
    | empty => empty
    | link(f, r) =>
      cases (List) r:
        | empty =>
          # The list has an odd number of elements
          [list: f]
        | link(fr, rr) =>
          # fr = first of rest, which we skip over
          # rr = rest of rest
          link(f, alternating(rr))
      end
  end
where:
  alternating([list: 1, 2, 3, 4, 5, 6]) is [list: 1, 3, 5]
  alternating([list:    2, 3, 4, 5, 6]) is [list: 2, 4, 6]
  alternating([list:       3, 4, 5, 6]) is [list:    3, 5]
  alternating([list:          4, 5, 6]) is [list:    4, 6]
end


fun max(lst :: List<Number>) -> Number:
  doc: "Return the max number in the list"
  cases (List) lst:
    | empty => raise("The list is empty")
    | link(f, r) =>
      cases (List) r:
        | empty => f
        | else  => num-max(f, max(r))
      end
  end
where:
  max([list: 1, 2, 3]) is 3
  max([list: 3, 1, 2]) is 3
  max([list: 1, 3, 2]) is 3
  max([list: 1, 2, 3]) is 3
end


#
# Approaches to list functions
#


# Explicit recursion version:

#|
fun sum-of-squares(lst :: List<Number>) -> Number:
  doc: "Add up the square of each number in the list"
  cases (List) lst:
    | empty => 0
    | link(f, r) => 
      (f * f) + sum-of-squares(r)
  end
where:
  sum-of-squares([list: ]) is 0
  sum-of-squares([list: 1, 2]) is 5
end
|#


# Using higher-order functions:

fun sum-of-squares(lst :: List<Number>) -> Number:
  doc: "Add up the square of each number in the list"
  M.sum(map(lam(x): x * x end, lst))
where:
  sum-of-squares([list: ]) is 0
  sum-of-squares([list: 1, 2]) is 5
end


fun avg(lst :: List<Number>) -> Number:
  doc: "Compute the average of the numbers in lst"
  M.sum(lst) / length(lst)
where:
  avg([list: 1, 2, 3, 4]) is 10/4
  avg([list:    2, 3, 4]) is  9/3
  avg([list:       3, 4]) is  7/2
  avg([list:          4]) is  4/1
end