Basic Syntax_Haskell Notes 1

I. Introduction

Haskell is a purely functional programming language, with no dispute about the purity of its functional characteristics

Imperative languages require you to provide steps for solving, while Haskell tends to let you provide descriptions of the problem

• Non-functional thinking: Tell the computer what to do through commands, for example, summation is traversing all numbers through loop structure, adding them up and recording the sum

• Functional thinking: Describe what the problem is through functions, for example, summation is adding the first number to the sum of the rest

P.S. For differences in thinking patterns, please see A Baptism of Functional Thinking Pattern

Haskell's characteristics:

• Variables are immutable: Variables in functional programming are the same as constants concept, originating from mathematical thinking, let x=1, then x is always 1

• Referential transparency: Function calls can be directly replaced with corresponding values without affecting function behavior. That is, functions are only used for evaluation, no side effects (won't affect external state), same input always gets same output

• Lazy evaluation: Calculate only when value is really needed, so at this time a series of calculations (function calls) are just a series of transformation formulas acting on input data, specifically looking at array.map().filter().reduce() only needs to traverse array once, not 3 times

• Static typing: Compiler does static type checking, nothing strange about this, but also supports powerful automatic type inference, so in most cases no need to declare types, this way having benefits of static type checking while ensuring code conciseness

P.S. Detailed explanation of referential transparency (Referential transparency):

An expression is said to be referentially transparent if it can be replaced with its corresponding value without changing the program's behavior. As a result, evaluating a referentially transparent function gives the same value for same arguments. Such functions are called pure functions. An expression that is not referentially transparent is called referentially opaque.

II. Basic Operations

Negative Numbers and Unary Minus

-3

Represents using unary operator - on number 3, getting its opposite -3. That is, - in -3 is not part of numeric literal, but an operator

2 + -3

Will get error:

cannot mix '+' [infixl 6] and prefix `-' [infixl 6] in the same infix expression

Binary operators and unary operators cannot be mixed in same infix expression, this brings uncertainty during parsing (ambiguous, compiler doesn't know how to understand). So, empirical principle is to put parentheses around all negative number literals, like (-3)

P.S. Haskell has only one unary operator, which is unary minus -, specifically see Unary operator

Logical Operations

3 operators: AND (&&), OR (||), NOT (not)

Two Bool literals: True, False

Equality Judgment

• ==: Judge equal, can be used for strings

• /=: Judge not equal (mathematician's language, so not-equal sign looks like this)

Note, types must be strictly consistent to compare, otherwise error reporting no comparability (1 == True will error), but considers integer and float comparable (1 == 1.0 is True)

Operator Precedence

In GHCi environment can use :info command to check operator precedence, for example:

> :i *
class Num a where
  ...
  (*) :: a -> a -> a
  ...
    -- Defined in 'GHC.Num'
infixl 7 *

> :i -
class Num a where
  ...
  (-) :: a -> a -> a
  ...
    -- Defined in 'GHC.Num'
infixl 6 -

Multiplication has higher precedence than subtraction (respectively 7 and 6), both are infix functions (infixl's infix), both are left-associative (infixl's l represents left associative), function signatures are also same (Num a => a -> a -> a)

Precedence range is 0-9, larger value means higher priority

P.S. infixl 7 * is called fixity declaration, used to specify operator (function) associativity and precedence, for example:

infixr 5 <+
x <+ xs = x : xs
infixl 5 +>
x +> xs = xs ++ [x]

Declared 2 custom infix operators <+ and +>, respectively right-associative and left-associative, both precedence 5 (same as :)

III. Function Calls

Syntax Format

Function calls in Haskell default to prefix syntax, for example:

succ 2
min 1 (-2)

Same as Bash script function call syntax, function_name argument1 argument2

But operators as special functions, default to be called in infix form, for example:

1 + 2

Actually, any function (including operators), can be called in prefix or infix form, rules as follows:

--  Prefix to infix
prefixFunc a b
a `prefixFunc` b

--  Infix to prefix
a infixFunc b
(infixFunc) a b

For example:

1 `min` (-2)
(+) 1 2

Dollar Function

$ is also a function:

($)
forall (r :: GHC.Types.RuntimeRep) a (b :: TYPE r).
(a -> b) -> a -> b
    -- Defined in 'GHC.Base'
infixr 0 $

Lowest precedence infix right-associative function, from signature, just a function call symbol, equivalent to adding parentheses on right:

-- Sum of squares of natural numbers, how many when exceeds 1000
length (takeWhile (< 1000) (scanl (+) 0 (map sqrt [1..])))
-- Equivalent to
length $ takeWhile (< 1000) $ scanl (+) 0 $ map sqrt [1..]

Lowest precedence, doesn't affect calculation, only adjusts calculation order:

> max 5 3 * 2 + 1
11
> max 5 $ 3 * 2 + 1
7

Simply understanding $ as parenthesis substitute is inappropriate, for example:

> 3 * $ 5 - 2 + 1

<interactive>:21:5: error:
    parse error on input '$'
    Perhaps you intended to use TemplateHaskell

Change posture:

> (3 *) $ 5 - 2 + 1
12

Because $ is an infix function, requires function on left, its parameter on right

P.S. There's also a very interesting thing: ($ 2) sqrt, a small trick of infix function currying

Currying

Haskell functions default to curried, all accept only one parameter:

In Haskell, all functions are considered curried: That is, all functions in Haskell take just one argument.

For example:

> :t (/)
(/) :: Fractional a => a -> a -> a
> :t (/ 2)
(/ 2) :: Fractional a => a -> a

Among them, (/ 2) is partial application of (/) :: Fractional a => a -> a -> a function, so didn't get calculation result, but returned function (/ 2) :: Fractional a => a -> a

P.S. (-) function is special, because (- 2) represents negative 2, doesn't return new function, if must, use (subtract 2)

Can use curry and uncurry functions for currying or uncurrying:

-- uncurry
> :t uncurry (/)
uncurry (/) :: Fractional c => (c, c) -> c
> (uncurry (/)) (4, 2)
2.0

-- curry
> :t curry (uncurry (/))
curry (uncurry (/)) :: Fractional c => c -> c -> c
> (curry (uncurry (/))) 4 2
2.0

Note: Multi-parameter functions need to pass parameters as tuple, for example f (4, 2)

When using currying characteristics also need to pay attention to parameter order, for example:

> (/ 2) 4
2.0
> (2 /) 4
0.5

Partial Application

Partial application and currying's biggest difference is impact on parameter count, from perspective of calling function for evaluation, currying doesn't change parameter count, while partial application reduces parameter count, because pre-filled several, for example:

fn (a, b) = a + b
curriedFn = curry fn
partialFn = curriedFn 2

// Call function for evaluation
fn (2, 3)
--  Add parentheses to make associativity clearer
(curriedFn 2) 3
partialFn 3

So, their connection is, can create partial functions through curried functions (partialFn = curriedFn 2). Difference is purpose, partial application is to reduce function's required parameter count (by fixing some parameter values), currying is to convert multi-parameter function to single-parameter function, this single-parameter function returns another single-parameter function (parameter count insufficient), or evaluates (parameter count sufficient)

IV. Function Declarations

doubledouble x = double (double x)

double x = x * 2
isEven x = x - x `div` 2 * 2 == 0
x `mod'` y = x - (x `div` y) * y

Format similar to function calls, function name plus space-separated parameter list, = followed by function body

2 characteristics:

• Declaration order doesn't matter

• Function name first letter cannot be uppercase, cannot start with digit

P.S. In mathematics, similar things use x x' x'' naming convention, can do same in Haskell:

y x = x ^ 2
y' x = x ^ 2 + 1

Also, infix form conversion can also be used in function declarations:

x `mod'` y = x - (x `div` y) * y

Can improve function declaration readability in some scenarios

Parameterless Functions

Constants can be understood as parameterless functions, for example:

> :t 2
2 :: Num t => t

Or more vivid example:

-- Parameterless function, just const
two = 1 + 1

Anonymous Functions

Anonymous functions are function expressions, called lambda in Haskell. Syntax format as follows:

backslash + parameter list -> function body

For example:

sum' = \x y -> x + y

P.S. Similar to JS's const sum = (x, y) => x + y

From application scenario perspective, lambda characteristics are:

• Use and discard: Doesn't require reuse

• Simple enough: Self-explanatory, can understand function at a glance from function body

For example:

map (\x -> x + 1) [1, 2, 3]
map (\([x, y]) -> x + y) [[1, 1], [2, 2], [3, 3]]

But many times don't need to explicitly create functions through lambda syntax, can fully utilize currying, List Comprehension and other characteristics:

map (+1) [1, 2, 3]
[ x + y | [x, y] <- [[1, 1], [2, 2], [3, 3]]]

Also, there's an interesting thing:

addThree = \x -> \y -> \z -> x + y + z
-- Because haskell comes with currying, so equivalent to
-- addThree x y z = x + y + z

P.S. -> in anonymous functions has same semantics as -> in type declarations, both represent "maps to"

Function Composition

Function composition expression in mathematics is f·g(x) = f(g(x)), Haskell similar:

fg = f . g

Operator used is .:

(.) :: (b -> c) -> (a -> b) -> a -> c 	-- Defined in 'GHC.Base'
infixr 9 .

Right-associative, so f . g . h x equivalent to f (g (h x)):

((/7) . (*2) . (+3)) 4

Function composition can be used to create new functions, and can extract parameters, for example:

-- f x = 2 * (sqrt x) + 1
-- Corresponding pointfree style
f = (+ 1) . (* 2) . sqrt

Extract inner parameters through composition, and utilize currying characteristics to remove. This function style obtained only through function composition, not involving actual parameters, is called pointfree style

P.S. Note, very long function chains reduce readability, not encouraged, should use let/where and other declarations to break function chains and give semantics

V. Conditional Statements and Pattern Matching

Conditional Statements

-- if then else
gt3 x = if x > 3
  then True
  else False

Note: if-then-else complete structure, else part cannot be omitted

Interestingly, if statement is also expression, so can do this:

lt10 x = if x < 10 then True else False
gte10 x = not (if x < 10 then True else False)

Pattern Matching

Pattern matching is basic function call mechanism, for example:

sayOneTwoThree :: (Integral a) => a -> String
sayOneTwoThree x = "Not between 1 and 3"
sayOneTwoThree 1 = "One!"
sayOneTwoThree 2 = "Two!"
sayOneTwoThree 3 = "Three!"

When calling function will match parameter types in declaration order, so above sayOneTwoThree 2 will only return "Not between 1 and 3"

Another example using pattern matching for recursive factorial:

fact 0 = 1
fact n = n * fact (n - 1)

Note, if pattern matching fails, will error:

mod10 0 = 0
mod10 1 = 1
-- If don't use universal match at end, mod10 2 will error
-- mod10 x = x `mod` 10

When matching fails:

> mod10 2
*** Exception: t.hs:(27,1)-(28,11): Non-exhaustive patterns in function mod10

Prompt mod10 function pattern definition has omissions

Besides used for function parameter definitions, pattern matching can also be used in List Comprehension and let-in expressions, where clauses and other scenarios, for example:

[ x + y | (x, y) <- [(1, 2), (3, 4)] ]
sumOneTwoThree = let (a, b, c) = (1, 2, 3) in a + b + c

Common pattern matching techniques as follows:

--  Split list head and tail, requires length >= 1, otherwise error
x:xs
--  Split list first two elements and tail
x:y:ys
--  Split while keeping original reference
xs @(x:y:ys)

P.S. @ keeping original reference called as pattern

Guard

A simple guard pattern example:

plus'' a b
  | a > 0, b > 0 = "sum is a positive value"
  | a < 0, b < 0 = "sum is a negative value"
  | otherwise = "what?"

After parameter list added | condition represents different function body branches, when called satisfies condition executes corresponding function body and returns, otherwise checks down in order

Note, final otherwise is interesting, because:

> :i otherwise
otherwise :: Bool 	-- Defined in 'GHC.Base'
> otherwise == True
True

So otherwise is just for semantics, directly using True as default branch condition is also fine

P.S. Single-line form is also legal (but poor readability, not recommended), for example:

isPositive n | n > 0 = True | otherwise = False

where Keyword

where keyword follows guard, used to define variables needed in function declarations, and helper functions

checkArea r
  | area < little = addSpace "little circle" ++ wrap sArea
  | area < normal = addSpace "normal circle" ++ wrap sArea
  | otherwise = addSpace  "big big circle" ++ wrap sArea
  where area = pi * r ^ 2
        -- !Must align, a bit silly
        --little = 10
        --normal = 50
        -- Can use pattern matching in where
        (little, normal) = (10, 50)
        sArea = show area
        -- Can define functions
        addSpace s = ' ' : s
        -- where can nest, define helper functions in helper functions
        wrap s = wrapLeft (wrapRight s)
          where wrapLeft s = " " ++ s
                wrapRight s = s ++ " "

Several characteristics of where clauses:

• Multi-line declarations must align indentation, otherwise compiler cannot parse correctly (doesn't know if variables/functions list to define has ended)

• Variables and functions declared in clause have scope of current function and its guard, and doesn't include other patterns of same-name functions

• Can use pattern matching in clause

• Allows nested use, helper functions can also declare needed variables and helper functions in their own where clauses

Note, where is a syntax structure, used to declare variables/functions at function bottom, scope is entire function including guard

P.S. If must single-line, can use semicolons to separate multiple declarations, for example:

sayHello = hello ++ " " ++ greeting
  where hello = "Hi"; greeting = "girls"

let Keyword

Syntax format:

let [bindings] in [expressions]

For example:

cylinder r h =
    let sideArea = 2 * pi * r * h
        bottomArea = pi * r ^ 2
    in sideArea + 2 * bottomArea

-- Expression form general usage similar to JS destructuring assignment
oneTwoThree = let (a, b, c) = (1, 2, 3) in a + b + c

let-in function similar to where, both used to define local variables/functions, differences as follows:

• Form: let xxx in... and ...where xxx declaration position difference, let puts definition in front

• Syntax: let-in is expression, while where is syntax structure, former can be placed anywhere

• Scope: let-in scope restriction stricter, variables/functions defined in let part only visible to in part

Note, also requires multi-line declarations to be strictly aligned, if must single-line use semicolons to separate

P.S. in part of let-in can be omitted, scope extends to current function/List Comprehension, if in GHCi environment, visible throughout entire interaction process

Case Expressions

Most common case expression is pattern matching of parameters when defining functions (sugar syntax of case expressions):

tail' [] = "empty list"
tail' [x] = "no tail"
tail' (_:xs) = show xs

Equivalent to

tail'' xs = case xs of  [] -> "empty list"
                        [x] -> "no tial"
                        (_:xs) -> show xs

Syntax format as follows:

case expression of  pattern -> result
                    pattern -> result
                    pattern -> result
                    ...

Use expression to try matching pattern in order, if match succeeds execute corresponding code block and return result, otherwise try next, if none match error

P.S. Similarly, as expression, case-of can be used anywhere, much more flexible than pattern matching (pattern matching can only be used in specific scenarios like function declarations, where, let, List Comprehension, etc.)

VI. Data Structures

List

List in Haskell is single-type array, for example:

emptyArr = []
numbers = [1, 2, 3, 4]
chars = ['a', 'b', 'c']

Actually, strings are List of Char type elements, for example:

> str = "okay"
> :i str
str :: [Char] 	-- Defined at <interactive>:51:1

> charArr = ['o', 'k', 'a', 'y']
> :i charArr
charArr :: [Char] 	-- Defined at <interactive>:54:1

So, string literals are just List syntax sugar

List Operations

++ concatenation:

> "Is life always this hard" ++ " ,or is it just when you are a kid ?"
"Is life always this hard ,or is it just when you are a kid ?"
--  Or
> ['A', 'l', 'w', 'a', 'y', 's'] ++ [' '] ++ "like this."
"Always like this."

Note, ++ operation traverses left List, so performance not high

: left insertion:

> 0 : [1, 2, 3]
[0,1,2,3]

Also, [1, 2, 3] is actually syntax sugar of 1 : 2 : 3 : [], : right-associative gets complete List

!! get element by index:

> "hello there" !! 4
'o'
> "hello there" !! 14
*** Exception: Prelude.!!: index too large

Index starts from 0, out of bounds will error

Multi-dimensional Arrays

> [[1], [2, 3]] !! 1 !! 1
3

Allows jagged arrays, also requires consistent element types

List Comparison

If elements in List are comparable, then List is comparable (traverse compare each element):

> "hello" == ['h', 'e', 'l', 'l', 'o']
True
> "0110" > "0101"
True

Common Functions

--  head get first element
> head [1, 2, 3]
1
--  tail get tail (remove first element)
> tail [1, 2, 3]
[2,3]
--  last get last element
> last [1, 2, 3]
3
--  init get body (remove last element)
> init [1, 2, 3]
[1,2]

Note: If List is empty, these 4 functions will error

--  length get array length
> length [1, 2]
2
--  null check empty
> null []
True
--  reverse flip head to tail
> reverse [1, 3, 2]
[2,3,1]
--  take get first n elements
> take 5 [1, 2]
[1,2]
--  drop remove first n elements
> drop 5 [1, 2]
[]

take/drop out of bounds won't error

--  maximum get max value
> maximum [1, -2, 3 , 0]
3
--  sum get sum
> sum [1..10]
55
--  elem check inclusion
> 3 `elem` [1, 2]
False

Among them [1..10] is Range syntax, elem called in infix form更符合 semantic habits

Range

A convenient way to generate enumerable List, for example:

> [1..7]
[1,2,3,4,5,6,7]
> ['A'..'Z']
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"

Allows specifying interval (step) through first two items, can be negative interval (descending sequence):

> [1, 3..7]
[1,3,5,7]
> [10, 9..1]
[10,9,8,7,6,5,4,3,2,1]

Floats have precision problems, not recommended to use in Range:

> [0.1, 0.3..1]
[0.1,0.3,0.5,0.7,0.8999999999999999,1.0999999999999999]

Also allows infinite sequences, for example:

--  Range without upper limit
> take 3 [1..]
[1,2,3]
--  Or cycle function infinite repeat
> take 7 (cycle [1..3])
[1,2,3,1,2,3,1]
--  Or repeat generate single element infinite repeat List
> take 6 (repeat 3)
[3,3,3,3,3,3]
--  Previous line result equivalent to
> replicate 6 3
[3,3,3,3,3,3]

List Comprehension

List comprehension refers to generating another List from existing List according to certain rules. So scenarios needing map, filter etc. operations can all be completed with List Comprehension

Syntax form similar to mathematical set definition, for example using set to describe even numbers within 10 as S = {2 * x | x <- N, x <= 5}, corresponding List Comprehension syntax as follows:

> [ 2 * x | x <- [1..5] ]
[2,4,6,8,10]

P.S. Use <- to represent belongs to symbol, very vivid

Can also add more restrictions (predicate):

> [ 2 * x | x <- [1..5], 2 * x `mod` 3 == 1, x `mod` 5 /= 0 ]
[4]

Besides adding restrictions to filter, can also declare variables/functions through let:

> [ doubleX | x <- [1..5], let doubleX =  2 * x, doubleX `mod` 3 == 1, x `mod` 5 /= 0 ]
[4]

P.S. If omit in part, declared variables/functions visible to restrictions and variables on its right, and left part of vertical line. If include, only affects current condition

More complex, for example finding all prime numbers from 1 to 100:

isPrime n = null [ x | x <- [2..n-1], n `mod` x == 0 ]
[ x | x <- [1..100], isPrime x ]

Looks no different from mathematical formulas, isPrime judgment rule is n cannot be evenly divided by any number in 2..n-1, set of all elements satisfying this judgment rule in 1 to 100 is what's sought

Like set definitions, elements can come from multiple existing sets, for example:

> [ x * y | x <- [1, 2, 3], y <- [4, 5] ]
[4,5,8,10,12,15]

Can use List Comprehension to implement own length function:

length' arr = sum [ 1 | x <- arr ]
--  Or more idiomatic
length' xs = sum [ 1 | _ <- xs ]

P.S. Among them _ represents placeholder, don't care what its value is, considered an idiomatic coding habit

Also, List Comprehension can be nested:

--  Filter out odd numbers in 2D array
[ [ x | x <- xs, even x ] | xs <- [[1,2], [3, 4]] ]
[[2],[4]]

Tuple

Tuples don't require single element type, from type constraint perspective, equivalent to structs

For example:

> :t (1, "Leon")
(1, "Leon") :: Num t => (t, [Char])
--  List requires single type, so putting binary and ternary tuples in one List will error
> [(1, "Leon"), (2, "Milk"), (3, "Little", "Girl")]
<interactive>:148:28: error:
    ? Couldn't match expected type '(t, [Char])'
                  with actual type '(Integer, [Char], [Char])'

Same as List, if elements in tuple are comparable, then same-type tuples can also be compared

More complex example, finding all right triangles with all three side lengths as integers and less than or equal to 10, perimeter 24:

[ (a, b, c) | c <- [1..10], b <- [1..c], a <- [1..b], a + b + c == 24, a^2 + b^2 == c^2 ]

Note implied side length relationship: c >= b >= a, considered as deduplication rule

Common Functions

fst/snd get first/last element of binary tuple:

fst (1, 2)
snd (1, 2)

Note, these two functions can only be used for binary tuples. General tuples don't have similar utility functions, but can implement own through pattern matching:

-- Get first element of ternary tuple
first (x, _, _) = x

zip combine tuples from List:

> zip [1, 2] ['A', 'B', 'C']
[(1,'A'),(2,'B')]

Extra single elements will be discarded

Reference Materials

• Infix Functions In Haskell

• Currying

• Currying versus partial application (with JavaScript code)

• 4.4.2 Fixity Declarations: Operator precedence table