-
Notifications
You must be signed in to change notification settings - Fork 1
/
Chapter3Ex.hs
86 lines (58 loc) · 1.67 KB
/
Chapter3Ex.hs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
module Chapter3Ex where
{-
1. What are the types of the following values?
['a', 'b', 'c']
[Char] or String
('a', 'b', 'c')
(Char, Char, Char)
[(False, '0'), (True, '1')]
[(Bool, Char)]
([False, True], ['0', '1'])
([Bool], [Char])
([Bool], String)
[tail, init, reverse]
[[a] -> [a]]
2. What are the types of the following functions?
-}
tail' :: [a] -> [a]
tail' [] = error "empty"
tail' (x : xs) = xs
head' :: [a] -> a
head' [] = error "empty"
head' (x : xs) = x
second xs = head' (tail' xs)
-- second :: [a] -> a
swap (x, y) = (y, x)
-- swap :: (a, b) -> (b, a)
pair x y = (x, y)
-- pair :: a -> b -> (a, b)
double x = x * 2
-- double :: Num a => a -> a
reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x : xs) = reverse xs ++ [x]
palindrome xs = reverse' xs == xs
-- palindrome :: Eq a => [a] -> Bool
twice f x = f (f x)
-- twice :: (a -> b) -> a -> b
{-
3. Check your answers to the preceding two questions using ghci.
4. Why is it not feasible in general for function types to be instances of the Eq
class? When is it feasible? Hint: two functions of the same type are equal if
they always return equal results for equal arguments.
Why?
Because of the Halting Problem
When?
If someone solved the Halting Problem
-}
-- considering a machine with infinite resources and not affected by external factors
fnHaltsImmediately :: Int -> Int
fnHaltsImmediately n = n + 3
fnHaltsForSomeTime :: Int -> Int
fnHaltsForSomeTime n | (foldl (+) 0 [1..n]) > 0 = n + 3
| otherwise = n + 3
fnDoesNotHalt :: Int -> Int
fnDoesNotHalt n = fnDoesNotHalt n
willFnHalt :: (Int -> Int) -> Int -> Bool
willFnHalt f n | f n > 0 = True
| otherwise = True