# CSCI0190 (Fall 2018)
provide *

import shared-gdrive("map-reduce-support.arr",
  "1F87DfS_i8fp3XeAyclYgW3sJPIf-WRuH") as support
import lists as L

type Tv-pair = support.Tv-pair
tv = support.tv
wc-map = support.wc-map
wc-reduce = support.wc-reduce

# DO NOT CHANGE ANYTHING ABOVE THIS LINE




fun count<A>(target :: A, a :: List<A>, eq-checker :: (A, A -> Boolean))
  -> Number:
  doc: "counts quantity of target in a"
  fun el-checker(el, cnt):
    if eq-checker(el, target):
      cnt + 1
    else:
      cnt
    end
  end
  a.foldl(el-checker, 0)
where:
  count(3, [list: 1, 2, 3], lam(x, a): x == a end) is 1
  count(3, [list: 3, 2, 3], lam(x, a): x == a end) is 2
  count(4, [list: 1, 2, 3], lam(x, a): x == a end) is 0
end

fun lst-same-els<A>(
    a :: List<A>,
    b :: List<A>,
    eq-checker :: (A, A -> Boolean))
  -> Boolean:
  doc: "checks whether two lists have the same elements in the same quantity"
  fun same-count(el, acc):
    acc and (count(el, a, eq-checker) == count(el, b, eq-checker))
  end
  (a.length() == b.length()) and a.foldl(same-count, true)
where:
  lst-same-els([list: 1, 2, 3], [list: 1, 2, 3], lam(x, a): x == a end)
    is true
  lst-same-els([list: 1, 2, 3], [list: 1, 2, 3], lam(x, a): x == a end)
    is true
  lst-same-els([list: 1, 2, 3], [list: 2, 1, 3], lam(x, a): x == a end)
    is true
  lst-same-els([list: 1, 2, 2], [list: 2, 1], lam(x, a): x == a end)
    is false
  lst-same-els([list: 1, 2, 2], [list: 2, 1, 1], lam(x, a): x == a end)
    is false
end




## A. Your map-reduce definition

fun map-reduce<A,B,M,N,O>(input :: List<Tv-pair<A,B>>,
    mapper :: (Tv-pair<A,B> -> List<Tv-pair<M,N>>),
    reducer :: (Tv-pair<M,List<N>> -> Tv-pair<M,O>)) -> List<Tv-pair<M,O>>:
  doc:```Applies the mapper function on every tv-pair in input, then reduces all
  the mapper outputs to a list of tv-pair outputs organized by tags```
  #first: apply the mapper function to every tv-pair in the input
  #this will result in a List<List<Tv-pair<M,N>>>
  mapped-inputs = map(mapper, input)

  #second: extract the inputs from list of list of tv-pairs into a
  #List containing every tv-pair
  #this will result in a List<Tv-pair<M, N>>
  extracted-inputs = extract-all-tv-pairs(mapped-inputs)

  #third: organize all inputs by tags and a list of all its values
  #this will result in a List<Tv-pair<M, List<N>>>
  organized-inputs = organize-all-tv-pairs(extracted-inputs)

  #fourth: apply the reducer function to every tag and a list of its values
  #into a tag and a single value, return that output
  #this will result in a List<Tv-pair<M, O>>
  map(reducer, organized-inputs)

where:
  nothing
end

#map-reduce helper functions
fun extract-all-tv-pairs<M,N>(all-tv-pairs :: List<List<Tv-pair<M, N>>>)
  -> List<Tv-pair<M, N>>:
  doc:```extracts the tv-pairs from every inner list in all-tv-pairs
  into a single list```
  cases (List) all-tv-pairs:
      #if outer list empty, have traversed through every tv-pair, return empty
    | empty => empty
      #i.e. all-tv-pairs has more elements
    | link(flists, rlists) =>
      #add all first list elements to extracted rest of lists
      L.append(flists, extract-all-tv-pairs(rlists))
  end
where:
  #base cases: ensure that doubly nested list produces single list
  extract-all-tv-pairs(empty) is empty
  extract-all-tv-pairs(
    [list:
      [list: ]]) is [list: ]
  #all lists in single inner list
  extract-all-tv-pairs(
    [list:
      [list:
        tv("Hi", "there")]])
    is [list: tv("Hi", "there")]
  extract-all-tv-pairs(
    [list:
      [list:
        tv("Hi", "there"),
        tv("Hello", "there")]])
    is [list: tv("Hi", "there"), tv("Hello", "there")]
  #all elements in different lists
  extract-all-tv-pairs(
    [list:
      [list:
        tv("Hi", "there"),
        tv("Hello", "there"),
        tv("good", "day")],
      [list:
        tv("Hello", "friend"),
        tv("Hello", "family"),
        tv("ahoy", "captain")]])
    is [list: tv("Hi", "there"), tv("Hello", "there"), tv("good", "day"),
    tv("Hello", "friend"), tv("Hello", "family"), tv("ahoy", "captain")]
  #longer lists, with some emptys
  extract-all-tv-pairs(
    [list:
      [list:
        tv("Hi", "there"),
        tv("Hello", "there"),
        tv("good", "day")],
      [list:
        tv("abc", "def"),
        tv("zyx", "tuv"),
        tv("live", "laugh")],
      [list: ],
      [list: ],
      [list:
        tv("Hello", "friend"),
        tv("Hello", "family"),
        tv("ahoy", "captain")]])
    is [list: tv("Hi", "there"), tv("Hello", "there"), tv("good", "day"),
    tv("abc", "def"), tv("zyx", "tuv"), tv("live", "laugh"),
    tv("Hello", "friend"), tv("Hello", "family"), tv("ahoy", "captain")]
end

fun organize-all-tv-pairs<M,N>(all-tv-pairs :: List<Tv-pair<M, N>>)
  -> List<Tv-pair<M, List<N>>>:
  doc:"organizes tv pairs with like tags to contain a list of their values"
  cases (List) all-tv-pairs:
      #if empty, have traversed through every all-tv-pair
    | empty => empty
    | link(fpair, rpair) =>
      first-tag = fpair.tag
      #collects all tv-pairs where tv.tag = first-tag from rest
      same-tag-as-first =
        filter(
          #lambda checks if x.tag is same as first.tag
          lam(x :: Tv-pair) -> Boolean: x.tag == first-tag end,
          all-tv-pairs)

      #organizes all tv-pairs with common tag into list of their vals
      collect-all-vals =
        map(
          #lamdba extracts values from tv-pair
          lam<A>(x :: Tv-pair) -> A: x.value end,
          same-tag-as-first)

      #creates new-tv-pair using the first-tag and the list of their values
      new-tv-pair = tv(first-tag, collect-all-vals)

      #removes pairs with same tag as first and recurs on it
      diff-tag-than-first =
        filter(
          #lambda checks if x.tag is not same as first.tag
          lam(x :: Tv-pair) -> Boolean: not(x.tag == first-tag) end,
          rpair)
      link(new-tv-pair, organize-all-tv-pairs(diff-tag-than-first))
  end
where:
  #base case: empty list
  organize-all-tv-pairs([list: ])
  #all tv-pairs have distinct tags
  organize-all-tv-pairs(
    [list: tv("Hello", "hi")])
    is [list: tv("Hello", [list: "hi"])]
  organize-all-tv-pairs(
    [list: tv("Hello", "hi"), tv("hola", "hey"), tv("ahoy", "friend")])
    is [list:
    tv("Hello", [list: "hi"]),
    tv("hola", [list: "hey"]),
    tv("ahoy", [list: "friend"])]
  #ensure that tv-pairs does not mix up tag with value
  organize-all-tv-pairs(
    [list: tv("Hello", "hi"), tv("hola", "hi"), tv("ahoy", "hi")])
    is [list:
    tv("Hello", [list: "hi"]),
    tv("hola", [list: "hi"]),
    tv("ahoy", [list: "hi"])]
  #tv-pairs share some tags
  organize-all-tv-pairs(
    [list:
      tv("Hi", "there"), tv("Hello", "there"), tv("good", "day"),
    tv("Hello", "friend"), tv("Hello", "family"), tv("ahoy", "captain")])
    is [list:
    tv("Hi", [list: "there"]),
    tv("Hello", [list: "there", "friend", "family"]),
    tv("good", [list: "day"]),
    tv("ahoy", [list: "captain"])]
  organize-all-tv-pairs([list: tv("Hi", "there"), tv("Hello", "there"),
      tv("good", "day"), tv("abc", "def"), tv("zyx", "tuv"),
      tv("Hi", "laugh"), tv("Hello", "friend"), tv("Hello", "family"),
      tv("zyx", "captain"), tv("abc", "alphabet")])
    is [list:
    tv("Hi", [list: "there", "laugh"]),
    tv("Hello", [list: "there", "friend", "family"]),
    tv("good", [list: "day"]),
    tv("abc", [list: "def", "alphabet"]),
    tv("zyx", [list: "tuv", "captain"])]
end

fun anagram-map<A,B,M,N>(tv-input :: Tv-pair<A,B>) -> List<Tv-pair<M,N>>:
  doc: ```Mapper for anagram, splits the list of words (value) and maps a tv
       with a tag of a alphabetized word onto each one```
  split-values = string-split-all(tv-input.value, " ")
  split-values.map(lam(x): tv-producer(x) end)
end

fun tv-producer<M,N>(string-input :: String) -> Tv-pair<M,N>:
  doc: ```Generates the new tv for the given string, with the tag being the
       alphabetized string, and the value being the string itself.```
  num-string = string-to-code-points(string-input)
  sorted-num-string = num-string.sort()
  sorted-tag = string-from-code-points(sorted-num-string)
  tv(sorted-tag, string-input)
end

check "anagram-map tests":
  #Single-case
  anagram-map(tv("file1", "a")) is [list: tv("a", "a")]
  #Case with multiple tvs
  anagram-map(tv("file1", "box cat dog Sass")) is
  [list: tv("box", "box"), tv("act", "cat"), tv("dgo", "dog"),
    tv("Sass", "Sass")]
  anagram-map(tv("file1", "obx act odg aSss")) is
  [list: tv("box", "obx"), tv("act", "act"), tv("dgo", "odg"),
    tv("Sass", "aSss")]
  #Case with repetition (identical and permutations)
  anagram-map(tv("file1", "box obx oxb xob obx")) is
  [list: tv("box", "box"), tv("box", "obx"), tv("box", "oxb"), tv("box", "xob"),
    tv("box", "obx")]
end

fun anagram-reduce<M,N,O>(input-tv :: Tv-pair<M, List<N>>)
  -> Tv-pair<M, O>:
  doc: ```Reducer for anagram. Essentially just deletes duplicate strings from
       each list```
  tv(input-tv.tag, L.distinct(input-tv.value))
end

fun anagram-list(tv-pair :: List<Tv-pair>)
  -> List<List>:
  doc: "Converts a list of tv-pair to a list of their values"
  cases (List) tv-pair:
    | empty => empty
    | link(f, r) => link(f.value, anagram-list(r))
  end
end

check "anagram-list checks":
  #Checks the base case
  anagram-list(empty) is empty
  #Checks the single case
  anagram-list([list: tv("box", [list: "Obx"])]) is [list: [list: "Obx"]]
  #Checks a more complex case
  anagram-list([list:
      tv("box-group", [list: "box", "obx", "oxb", "xob", "bxo"]),
      tv("cat-group", [list: "cat", "act", "atc", "tac"])]) is
  [list: [list: "box", "obx", "oxb", "xob", "bxo"],
    [list: "cat", "act", "atc", "tac"]]
end

fun is-equiv(new-tv :: List<String>, new-check-list :: List<List>)
  -> Boolean:
  doc: "Checks if a tv's list is inside the list of tv-lists"
  cases (List) new-check-list:
    | empty => false
    | link(f, r) =>
      lst-same-els(new-tv, f, lam(x, a): x == a end) or is-equiv(new-tv, r)
  end
end

check "is-equiv checks":
  #Checks the base case
  is-equiv(empty, [list: [list: "box", "obx", "oxb", "xob", "bxo"]]) is false
  #Checks for case-variations changes between inputs
  is-equiv([list: "box", "obx", "oxb", "xob", "bxo"],
    [list: [list: "bOx", "obx", "oxb", "xob", "bxo"],
      [list: "cat", "act", "atc", "tac"]]) is false
  #Checks for variations in order
  is-equiv([list: "obx", "box", "bxo", "xob", "oxb"],
    [list: [list: "box", "obx", "oxb", "xob", "bxo"],
      [list: "cat", "act", "atc", "tac"]]) is true
end

fun anagram-check(tv-list :: List<Tv-pair>, check-list :: List<Tv-pair>)
  -> Boolean:
  doc: "Checks if the tv-list is equivalent to the expected check-list"
  a-list=anagram-list(tv-list)
  b-list=anagram-list(check-list)
  bool-list =
    a-list.map(lam(x): is-equiv(x, b-list) end)
  (not(bool-list.member(false)) and (a-list.length() == b-list.length()))
end

check "anagram-check":
  #Generic check for anagram-check
  anagram-check(map-reduce([list:
        tv("file1", "box cat dog Sass"), tv("file2", "obx act odg aSss"),
        tv("file3", "oxb atc ogd xob Ssas box"),
        tv("file4", "tac god bxo sass")],
      anagram-map, anagram-reduce),
    [list:
      tv("box-group", [list: "box", "obx", "oxb", "xob", "bxo"]),
      tv("cat-group", [list: "cat", "act", "atc", "tac"]),
      tv("dog-group", [list: "dog", "odg", "ogd", "god"]),
      tv("Sass-group", [list: "Sass", "aSss", "Ssas"]),
      tv("sass-group", [list: "sass"])]) is true
  #Checks for character-case
  anagram-check(map-reduce([list:
        tv("file1", "box cat"), tv("file2", "oBx cAt act")],
      anagram-map, anagram-reduce),
    [list:
      tv("box", [list: "box"]),
      tv("act", [list: "cat", "act"]),
      tv("Act", [list: "cAt"]),
      tv("Box", [list: "oBx"])])
        is true
  anagram-check(map-reduce([list:
        tv("file1", "box cat"), tv("file2", "oBx cAt act")],
      anagram-map, anagram-reduce),
    [list:
      tv("box", [list: "box"]),
      tv("act", [list: "cat", "act", "cAt"]),
      tv("Box", [list: "oBx"])])
    is false
end

recommend(title :: String,
          book-records :: List<Tv-pair<String, String>)
  -> Tv-pair<Number, List<String>>