Comments

Again nice lecture!

 

A comment about implementing takeWhile and dropWhile using foldr. These are functions to take or drop elements at the beginning of a list. So, I think it would be easier to implement them using foldl (fold left). Can it be done with foldr? I’m not sure. The drawback to implement them with fold is that they would be useless when dealing with infinite lists. That is because fold(r|l) consume the whole list before producing a result.

 

Here is my take on both using foldl

takeWhile' :: (a -> Bool) -> [a] -> [a] takeWhile' p = snd . foldl (\(e,v) x -> if e then (e,v) else if p x then (False,v++[x]) else (True,v)) (False,[]) dropWhile' :: (a -> Bool) -> [a] -> [a] dropWhile' p = snd . foldl (\(e,v) x -> if
 e then (e,v++[x]) else if p x then (True,v) else (False,v++[])) (False,[]) 

 

Here is my take on the homework:

 

1.- Define:

 

and :

and' :: [Bool] -> Bool and' [] = True and' (False:_) = False and' (_:xs) = and xs 

 

concat:

concat' :: [[a]] -> [a] concat' [] = [] concat' (xs:xss) = xs ++ concat' xss

 

replicate:

replicate' :: Int -> a -> [a] replicate' 0 x = [] replicate' (n+1) x = x:replicate' n x

 

Select the Nth statement of a list:

(!!@) :: [a] -> Int -> a (!!@) (x:_) 0 = x (!!@) (_:xs) (n+1) = xs !!@ n

 

elem:

elem' :: (Eq a) => a -> [a] -> Bool elem' _ [] = False elem' x (y:ys) | x == y = True | otherwise = elem' x ys

 

2. Define merge :: [Int] -> [Int] -> [Int]

merge:: (Ord a) => [a] -> [a] -> [a] merge [] [] = [] merge xs [] = xs merge [] ys = ys merge (x:xs) (y:ys) | x < y = x:merge xs (y:ys) | x == y = x:y:merge xs ys | otherwise = y:merge (x:xs) ys

 

3. Define merge sort:

msort :: (Ord a) => [a] -> [a] msort [] = [] msort [x] = [x] msort xs = merge (msort ys) (msort zs) where [(ys,zs)] = halve xs halve :: [a] -> [([a],[a])] halve [] = [] halve xs = [(take n xs, drop n xs)] where n = (length xs `div` 2)

 

I'm having a blast with this series.

More homework:

1) Prove that fac n = recfac n

 

Definition of recfact n:

(1)        recfac 0 = 1

(2)        recfac (n+1) = (n+1) * recfact n

 

Definition of fac n:

(3)        fac n = product [1...n]

                        where

(4)                                product [] = 1

(5)                                product [1..n] = 1 * 2 * … (n-1) * n

 

We want to prove that:

                    fact n = recfac n

 

Using induction:

 

Case n = 0

            fac 0 = recfac 0

 

            fac 0 = 1 (Eq. 1)

 

            recfac 0 = product [1 .. 0] = product [] = 1 (Eq. 4)

 

            1 = 1

 

Case (m + 1):

(7)        fac (m+1) = recfac (m+1)

 

fac (m+1) = product [  1..(m+1)] = 1 * 2 *….* m * (m+1)

 

1. Using Eq.5:       1 * 2 *….* m  = product [1..m]

 

            fac (m+1) = 1 * 2 *….* m * (m+1)  =(product [1..m]) * (m+1)

 

(8)        fac (m+1) = (product [1..m]) * (m+1)

 

Using Eq 2 :  recfac (m+1) = (m+1) * recfac m

 

 

Replacing Eq 8 into Eq 7:

            fac (m+1) = (product [1..m]) * (m+1) = recfac (m+1)

 

Using Eq 2 on the right side:

            (product [1..m]) * (m+1) = (m+1) * recfac m

 

Dividing by (m+1) on both sides:

            product [1..m] = recfac m

 

Using Eq 3 on the left side:

            fac m = recfac m

 

Q.E.D.!

Again, nice lecture.  I'm lloking forward to the rest.

 

Here is my take on Append:

public static IEnumerable<T> Append<T>(this IEnumerable<T> a, IEnumerable<T> b) { foreach (var t in a) { yield return t; } foreach (var t in b) { yield return t; } } 

Here is my take on the homework:

 

1. Without looking at the definitions from the standard prelude, define the  following library functions using recursion.

 

- Decide if all logical values in a list are True:

and' :: [Bool] -> Bool and' [] = True and' (False:_) = False and' (_:xs) = and xs

 

- Concatenate a list of lists:

concat' :: [[a]] -> [a] concat' [] = [] concat' (xs:xss) = xs ++ concat' xss

 

- Produce a list with n identical elements:

replicate' :: Int -> a -> [a] replicate' 0 x = [] replicate' (n+1) x = x:replicate' n x

 

- Select the nth element of a list

(!!@) :: [a] -> Int -> a (!!@) (x:_) 0 = x (!!@) (_:xs) (n+1) = xs !!@ n

 

- Decide if a value is an element of a list:

elem' :: (Eq a) => a -> [a] -> Bool elem' _ [] = False elem' x (y:ys) | x == y = True | otherwise = elem' x ys

 

2. Define a recursive function merge:: Ord a => [a] -> [a] -> [a] that  merges two sorted lists to give a single sorted list.

merge:: (Ord a) => [a] -> [a] -> [a] merge [] [] = [] merge xs [] = xs merge [] ys = ys merge (x:xs) (y:ys) | x < y = x:merge xs (y:ys) | x == y = x:y:merge xs ys | otherwise = y:merge (x:xs) ys

 

3. Define a recursive function msort :: Ord a => [a] -> [a] that  implements merge sort

msort :: (Ord a) => [a] -> [a] msort [] = [] msort [x] = [x] msort xs = merge (msort ys) (msort zs) where [(ys,zs)] = halve xs halve :: [a] -> [([a],[a])] halve [] = [] halve xs = [(take n xs, drop n xs)] where n = (length xs `div` 2)

 

Here is my take on part of the homework

 

1. safetail

safetaila :: [a] -[a] safetaila xs = if null xs then [] else tail xs safetailb :: [a] -[a] safetailb xs | null xs = [] | otherwise = tail xs safetailc :: [a] -[a] safetailc [] = [] safetailc (_:xs) = xs 

2. Implement (||)  in three different ways

(||!) :: Bool -Bool -Bool True ||! True = True True ||! False = True False ||! True = True False ||! False = False (||@) :: Bool -Bool -Bool False ||@ False = False _ ||@ _ = True (||#) :: Bool -Bool -Bool False ||# b = b True ||# _ = True

3. Redefine (&&)

(&&$) a b = if a == True && b == True then True else False

4. Redefine (&&) again

(&&%) a b = if a == True then b else False

At last Thursday is here.

 

Excelent presentation as always. The only thing is that you missed an excelent opportunity to implement "where" using a list comprehension.

 

where' :: [a] -> (Int -> a -> Bool) -> [a] where' xs p = [x | (x,i) <- xs', p i x ] where xs' = zip xs [0..]

 

Thanks again.

I'm looking forward to the next lecture.

To get what  you want you can use the function flip that is on the haskell prelude.

 

The Haskell  prelude defines flip as:

-- flip f  takes its (first) two arguments in the reverse order of f.
flip             :: (a -> b -> c) -> b -> a -> c
flip f x y       =  f y x

 

using flip we can write (-1) 3 as:

 

(flip (-) 1) 3  

 

Also, the prelude has a substract function defined as:

 

subtract         :: (Num a) => a -> a -> a
subtract         =  flip (-)

 

I love the “back to school” feeling I get with these lectures. I like Novox have been waiting all day for this. Keep up the good work

Here is part of the homework:

 

{-
1.- What type are the following values:
    ['a','b','c'] :: [Char]
    ('a','b','c') :: (Char,Char,Char)
    [(False,'0'),(True,'1')] :: [(Bool,Char)]
    ([False, True],['0','1']) :: ([Bool],[Char])
    [tail, init, reverse] :: [[a] -> [a]]
-}

-- 2.- What are the type of the following functions:

second :: [a] -> a
second xs = head (tail xs)

swap :: (a,b) -> (b,a)
swap (x,y) = (y,x)

pair:: a -> b -> (a,b)
pair x y = (x,y)

double :: (Num a) => a -> a
double x = x*2

palindrome :: (Eq a) => [a] -> Bool
palindrome xs = reverse xs == xs

twice :: (a -> a) -> a -> a
twice f x = f (f x)

 

Nice lecture, please keep up the good work!!!