# Programming Language Design Assignment \#4

In this assignment,
you're asked to create some simple functions in Haskell.

Please submit your answer
* in a **single file** named by your student ID\# (e.x. `107525008.hs`)
* **before the deadline(11/27 23:55)**

:::info
For one who don't want install GHC (which consume around 1.5 GiB of disk storage),
using online REPLs like [Repl.it](https://repl.it/) is a much easier alternative choice.

---

After you create a REPL, it should looks like


* You can write your function definition in the left panel
* Click the execute button to load them into GHCi
* You can try your functions in the right panel(the REPL)
:::

# more on Haskell
The following paragraphs only cover the minimal knowledge to complete this assignment, to learn more about Haskell, [Learn You a Haskell for Great Good](http://learnyouahaskell.com/chapters) is a recommended material.
## Lists

* To create lists, one can use the following syntax:

[True, False] -- has the type [Bool]
['a', 'b'] -- has the type [Char]
[1,2,3] -- has the type Num a => [a]
[] -- is the empty list

* there is also another way to create lists:

1:[] -- is same as [1]
'a':('b':('c':[])) -- is same as ['a', 'b', 'c']
'a':'b':'c':[] -- is same as above one since (:) has right associativity

* a list can only contain items with same type

[True, "hi"] -- results a Type Error

* a String is just a list of `Char`

"abc" -- is same as ['a', 'b', 'c']

* lists can be concatenate using `(++)`

[1,2,3] ++ [4,5,6] -- [1,2,3,4,5,6]
"abc" ++ "def" -- "abcdef"

## Function Definition/Application

In Haskell, there is no need to write parenthesis and commas to call a function:

~~~haskell
sum [1,2,3]
pow 2 3
~~~

And actually wrap your arguments in parenthesis and commas will have different meaning in Haskell:

~~~haskell
f 1 2 3 -- f :: Int -> Int -> Int -> Int
g (1,2,3) -- g :: (Int, Int, Int) -> Int
-- f and g are accepting different types of input
~~~

To create functions, one can use the following syntax:
~~~haskell
f :: Int -> Int -- type signature
f x = x + 1 -- f is the name, and x is the argument
~~~

In Haskell, compiler can infer type of a function, in most of cases, type signatures can be omitted.
~~~haskell
f x = x + 1
~~~

## Pattern Matching

Pattern Matching is a common language construct provided in functional programming languages.

f 0 = "zero"
f 1 = "one"
f n = "not 0 and not 1"

Besides strings/chars/numbers, it is also possible to match lists/tuples and any data type.
In Haskell, you can match lists like how you build them:

head' :: [a] -> a
head' [] = error "empty list"
head' (x:xs) = x

init' :: [a] -> [a]
init' [] = error "empty list"
init' (x:[]) = []
init' (x:xs) = x : init' xs

swap :: [a] -> [a]
swap [x] = error "list too short"
swap (x:y:xs) = (y:x:xs)

## Recursive Functions

In Haskell, there is no loop constructs and all variables are immutable,
which means tasks like `sum` needs to write in a different flavor.

For example, sum can be defined like this:

sum []     = 0
sum (x:xs) = x + sum xs

When evaluating `sum [1,2,3]`, it expands like this:

   sum [1,2,3]
== sum (1:2:3:[])
== 1 + sum (2:3:[])
== 1 + 2 + sum (3:[])
== 1 + 2 + 3 + sum []
== 1 + 2 + 3 + 0

# Exercise

Implement the following function use **only** pattern matching, recursive function calls, and the things given in the hints.

1. Implement your own `tail` function
~~~haskell
myTail :: [a] -> [a]
-- myTail [1,2,3] == [2, 3]
~~~
2. Implement your own `last` function
~~~haskell
myLast :: [a] -> a
-- myLast [1,2,3] == 3
~~~
3. Implement your own `reverse` function
~~~haskell
myReverse :: [a] -> [a]
-- myReverse [1,2,3] == [3, 2, 1]
~~~
:::info
hints:
* you may use `++` to concatenate reversed list.
:::
4. Implement `isPalindrome` which checks a list is palindrome or not
~~~haskell
isPalindrome :: Eq a => [a] -> Bool
-- isPalindrome [1,2,1] == True
-- isPalindrome [1,2,3] == False
-- isPalindrome [] == True
~~~
:::info
hints:
* you may use `reverse` or `myReverse`
:::
5. Implement `isPalindrome'` again but without using `reverse` this time

:::info
hints:
* you may use `head`, `tail`, `init`, `last` to get element/sub-lists
* you may use `a == b` to test equality of `a` and `b`
:::