---
# System prepended metadata

title: Programming Language Design Assignment \#4

---

# 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

![](https://i.imgur.com/STMDOFo.png)

* 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:

```haskell
[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:

```haskell
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

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

* a String is just a list of `Char`

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

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

```haskell
[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. 

```haskell
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:

```haskell
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:

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

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

```haskell
   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`
    :::