{-  CSci 450/503, Programming Languages
    Exam #3 Take-Home Component
    H. Conrad Cunningham
    2016-11-30: Original
    2016-12-04: Added more alternatives in comments
-}

import Html exposing (..)

    
{- (a) Function numof takes a value and a list and returns the number of
   occurrences of the value in the list.  
-}

numof : a -> List a -> Int
numof x ys =
     List.length (List.filter ((==) x) ys)

{- Alternative implementations of numof

-- Using function application operators to avoid parentheses. 
-- Think: pipes in Unix

numof x ys =
    List.length <| List.filter ((==) x) ys

numof x ys =
    List.filter ((==) x) ys |> List.length

-- Using function composition opertors.
-- Think: function composition in mathematics

numof x =
    List.length << List.filter ((==) x)

numof x =
    List.filter ((==) x) >> List.length 

-- Using backward recursion directly

numof : a -> List a -> Int
numof x xs =
    case xs of
      []    -> 0
      y::ys ->
          if x == y then
               1 + numof x ys
           else
               numof x ys

-- Using a tail recursive auxiliary function with an accumulating
-- paramter

numof : a -> List a -> Int
numof x xs =
    let
        count ys c =
          case ys of
              []    -> c
              z::zs ->
                   if z == x then
                       count zs (c+1)
                   else
                       count zs c
    in
        count xs 0

-- Using foldr to combine comparison and counting

numof x xs =
    List.foldr (\u v -> if u == x then v+1 else v) 0 xs

-}


{- (b) Function ellen takes a list of character strings and returns a
      list of the lengths of the corresponding strings.
-}

ellen : List String -> List Int
ellen xs =
    List.map String.length xs

{- Alternative implementations

ellen = 
    List.map String.length

-- Could also use directly recursive functions or a fold
-}


{- (c) Function ssp takes a list of integers and returns the sum of
       the squares of the positive elements of the list.
-}

sq x = x * x

ssp : List Int -> Int
ssp xs =
    List.foldr (+) 0 (List.map sq (List.filter ((<) 0) xs))

{- Alternative implementations

-- Using sum and an anonymous function

ssp xs =
    List.sum (List.map (\x => x*x) (List.filter ((<) 0) xs))
  
-- Using function composition

ssp =
    sum << List.map sq << List.filter ((<) 0)

-- Could also use >>, |>, <|, foldr, or directly recursive functions
-- as in Exercise (a).

-- Using a "sequence" of expressions

ssp xs =
    let
        positives = List.filter ((<) 0) xs
        squares   = List.map (\x -> x * x) positives
    in
        List.sum squares
-}


-- Tree algebraic data type

type Tree a = Leaf | Node a (Tree a) (Tree a) 

-- Code from in-class portion of Exam 3

inorder t =
    case t of 
      Leaf              -> []
      Node v left right -> inorder left ++ [v] ++ inorder right

sumtree t =
    case t of
      Leaf -> 0
      Node v left right -> v + sumtree left + sumtree right


{- (d) Function twist takes a tree and returns the tree with the left
       and right subtrees reversed for every node, but otherwise
       leaves the structure of the tree the same.
-}

twist : Tree a -> Tree a
twist t =
    case t of
      Leaf              -> Leaf
      Node v left right -> Node v (twist right) (twist left)


-- Simple Display Functions

newline = br [] []

displayLines : List String -> List (Html msg)
displayLines ss = 
    case ss of
      []      -> []
      x :: xs -> text x :: newline :: displayLines xs

display : List String -> Html msg
display ls = p [] (displayLines ls)


-- Some testing

list1 = [1,2,3,3,4,5,3,3,6]
list2 = [1,2]
list3 = ["Alpha", "Beta", "Gamma"]
list4 = [-1, 2, -1, 3, -4]

tree1 = Node 3 (Node 2 (Node 1 Leaf Leaf) Leaf) (Node 4 Leaf Leaf)

main =
  display 
      [ "Begin!"
      , "numof 3 list1 = " ++ toString (numof 3 list1)
      , "numof 3 list2 = " ++ toString (numof 3 list2)
      , "ellen list3   = " ++ toString (ellen list3)
      , "ellen []      = " ++ toString (ellen [])
      , "ssp list1     = " ++ toString (ssp list1)
      , "ssp list2     = " ++ toString (ssp list2)
      , "ssp list4     = " ++ toString (ssp list4)
      , "tree1         = " ++ toString (tree1)
      , "twist tree1   = " ++ toString (twist tree1)
      ]