In September of 1987 a meeting was held at the conference on Functional Programming Languages and Computer Architecture (FPCA ’87) in Portland, Oregon, to discuss an unfortunate situation in the functional programming community: there had come into being more than a dozen nonstrict, purely functional programming languages, all similar in expressive power and semantic underpinnings. There was a strong consensus at this meeting that more widespread use of this class of functional languages was being hampered by the lack of a common language. It was decided that a committee should be formed to design such a language, providing faster communication of new ideas, a stable foundation for real applications development, and a vehicle through which others would be encouraged to use functional languages. This document describes the result of that committee’s efforts: a purely functional programming language called Haskell, named after the logician Haskell B. Curry whose work provides the logical basis for much of ours.
The committee’s primary goal was to design a language that satisfied these constraints:
The committee intended that Haskell would serve as a basis for future research in language design, and hoped that extensions or variants of the language would appear, incorporating experimental features. Haskell has indeed evolved continuously since its original publication. By the middle of 1997, there had been four iterations of the language design (the latest at that point being Haskell 1.4). At the 1997 Haskell Workshop in Amsterdam, it was decided that a stable variant of Haskell was needed; this stable language is the subject of this Report, and is called “Haskell 98”.
Haskell 98 was conceived as a relatively minor tidy-up of Haskell 1.4, making some simplifications, and removing some pitfalls for the unwary.
除了函数的产生输出之外，其他因为调用函数而引起的其他效果都是 side effect 。
ex: 设置全局变量。屏幕打印，文件输入输出。
pure functional program has no side effect. pure funtional function produces the same results given the same argument.
destructive update: destroy first,then update
reference transparency: given same both to function f and g, they produce the same outputs, then f can be replaces by g or vice-verse.
函数和数据用小写开头的单词表示，type 用大写字母开头。
sub-problem and solveing them one by one but also hou to glue all solution of sub-problem together.
the right glue is as important as the modularisatioin.
the question is how to decompise the problems.
OO gives a kinds of glue. OO tends to separate them, they are highly depend how the abstraction model is.
** arithmetic ** tuple
(1,2), (1,2,3) are tuples. Tuple is allowed to be heterogenouse.
Pair is a tuple with only two elements. ``fst'' and ``snd'' are functions to extract the first and the second elements of a pair respectively.
** list
The expression of list like [1,2,3,4] is a syntax sugar, it means that 1:2:3:4:[], ":" means cons.
It is more readable than LISP, e.g.
(cons 1 (cons 2 (cons 3(cons 4 nil))))
I believe that they express the same meaning of contructing a list.
Lists must be homogenous.
``head'' function returns the first element of a list, like ``car'' in LISP.
``tail'' function returns the rest elements of a list, like ``cdr'' in LISP.
``length'' returns a length of a list.
``++'' opertor can concatenate two list.
** string
String is a list of char.
``show'' function can convert a value to a string.
``read'' can convert a string to a value.
Prelude>read "5" + 3 8
** simple List Functions
``map'' takes as arguments a list of values and a function that should be appied to each of the values.
Prelude> map Char.toUpper "Hello World" "HELLO WORLD"
``filter'' takes as arguments which are similar with ``map'', but the second function is a proposition. ``filter'' return a list which contains all elements in the list that meets the condition.
``foldr'' is similar with ``reduce'' in some lanugae.
; a list is (cons 1 (cons 2 (cons 3 (cons 4 nil)))) (reduce func init_value) ;; mean that replace cons with func and replace nil with init_value
``foldl'' goes the other way and effectivelly the opposite backeting.
foldl is often more efficient than foldr for reasons that we will discuss in Section 7.8. However, foldr can work on infinite lists, while foldl cannot. This is because before foldl does anything, it has to go to the end of the list. On the other hand, foldr starts producing output immediately. For instance, foldr (:) [] [1,2,3,4,5] simply returns the same list. Even if the list were in-finite, it would produce output. A similar function using foldl would fail to produce any output.
In hugs, ":load" or ":r" mean load file, and ":reload" or ":r" mean reload the file.
sqrt the square root function id the identity function: id x = x fst extracts the first element from a pair snd extracts the second element from a pair null tells you whether or not a list is empty head returns the first element on a non-empty list tail returns everything but the first element of a non-empty list ++ concatenates two lists == checks to see if two elements are equal /= checks to see if two elements are une
** Type classes
Both "Int" and "Double" are instances of "Num", and they are basic type.
A lots of basic types except for "function" are instances of "Show".
*** Lambda caculus \x = expr \x\y = expr
** pattern matching
** guard
NOTE: guards are tested AFTER pattern matching. If type is matched and all tests of guards are failed and there is no "otherwise" clause, an error popups.
** Let vs Where
Athough you can mix use them together, but don't do that
I prefer Where.
** Intance Declerations
** name field of datatype.
}
fieldname typename
func x = x { fieldname1 = ... }
func (typename_t { fieldname1=x,fieldname2=y })= ....
typename_t { fieldname1=x, fieldname2=y }
** infix and prefix
(infixfunc) = prefixfunc =
prefixfunc x y x infixfunc y x `prefixfunc` y (infixfunc) x y
** list comprehension
(++) = foldr ((.) . (:)) id map f = foldr ((:) . f) [] filter p = foldr (\a b -> if p a then a:b else b) [] concat = foldr (++) []
Recursion and Induction
base case and recursive case
lambda calculus
t ::= x -- variable
| lambda x. t -- abstraction
| t t -- application
the term of the form:
(lambda x. t1) t2
the term containing no beta redex.
FV, the set of free variable:
FV(x) = {x}
FV(lambda x. t) = FV{t} - {x}
FV(t1 t2) = FV{t1} U FV{t2}
EX:
FV(lambda x. y(lambda y. xyu))
= FV(y (lambda y. xyu)) - {x}
= FV(y) U FV(lambda y. xyu) - {x}
= {y} U { FV{xyu} - {y}} - {x}
= {y} U {x,u}- {x}
= {y,u}
The name of a bound variable does not matter. Change of bound variable name is called alph-conversion.
evaluate function before argument evaluate argument before applying function
Terms:
t :: = true
false
if t then t else t
0
succ t
pred t
iszero t
Values
v :: = true
false
nv
nv ::= 0
succ nv
f is strict iff the value of 'f bot' is "bottom". In other word if f is applied to a non-terminating expression, it also fails to terminate.
bot = bot
So "bot" is non-terminating function.
const1 x = 1
"const1" is not strict function, it is called "lazy function"