Functional Programming Concepts
Table of Contents
- 1. Concepts
- 1.1. Overview
- 1.2. First-Class Function
- 1.3. Pure Functions
- 1.4. Referential Transparency
- 1.5. Closure
- 1.6. Currying and Partial Application
- 1.7. Tail Call Optimization and Tail Recursive Functions
- 1.8. Fundamental Higher Order Functions
- 1.9. Lazy Evaluation
- 1.10. Terminology
- 1.11. Special Functions
- 1.12. Function Composition
- 1.13. Functors
- 1.14. Monads
- 2. Functional Languages
- 3. Influential People
- 4. Miscellaneous
- 5. Reading
1 Concepts
1.1 Overview
Functional Programming
Functional Programming is all about programming with functions.
Functional Programming Features
- Pure Functions / Referential Transparency / No side effect
- Function Composition
- Lambda Functions/ Anonymous Functions
- High Order Functions
- Currying/ Partial Function Application
- Closure - Returning functions from functions
- Data Immutability
- Pattern Matching
- Lists are the fundamental data Structure
Non Essential Features:
- Static Typing
- Type Inference
- Algebraic Data Types
Functional Programming Design Patterns
- Curry/ Partial function application - Creating new functions by holding a parameter constant
- Closure - Return functions from functions
- Pure Functions: separate pure code from impure code.
- Function composition
- Composable functions
- High Order Functions
- MapReduce Algorithms - Split computation in multiple computers cores.
- Lazy Evaluation ( aka Delayed evaluation)
- Pattern Matching
- Monads
1.2 First-Class Function
Functions can be passed as arguments to other functions, returned from functions, stored in variables and data structures and built at run time. The majority of languages supports first-class functions like Scheme, Javascript, Python, Haskell, ML, OCaml and many others some exceptions are C, Java, Matlab (Octave open source implementation), Bash, and Forth.
Functions can be passed as arguments and returned from functions
- Example in Python: The function f is passed as argument to the derivate function that returns a new function named _, that computes the derivate of f at x.
def derivate (f, dx=1e-5): def _(x): return (f(x+dx) - f(x))/dx return _ # Algebraic derivate: # # df(x) = 2*x - 3 # >>> def f(x): return x**2 - 3*x + 4 ... # Numerical derivate of f >>> df = derivate(f) >>> # Algebraic derivate of f >>> def dfa (x): return 2*x - 3 ... >>> ;; Functions can be stored in variables >>> func = f >>> func(5) 14 >>> >>> df = derivate(f) >>> df(3) 3.000009999887254 >>> df(4) 5.000009999633903 >>> >>> dfa(3) 3 >>> dfa(4) 5 >>> >>> f(3) 4 >>> f(10) 74 >>>
Functions can be stored in data structures
Example: Python - Functions stored in a dictionary hash-table
import math def myfun2(x): return 5.68 * x - 5.0 dispatchTable = { "sin": math.sin, "cos": math.cos, "exp": math.exp, "tan": math.tan, "myfun": lambda x: 10.2 * x - 5.0, "myfun2": myfun2 } >>> dispatchTable["sin"](math.pi) 1.2246467991473532e-16 >>> dispatchTable["cos"](math.pi) -1.0 >>> dispatchTable["tan"](math.pi) -1.2246467991473532e-16 >>> dispatchTable["exp"](math.pi) 23.140692632779267 >>> >>> >>> dispatchTable["exp"](1.0) 2.718281828459045 >>> >>> >>> dispatchTable["myfun"](1.0) 5.199999999999999 >>> dispatchTable["myfun2"](1.0) 0.6799999999999997
Example: Haskell - Functions stored in a list.
> let funlist = [sin, cos, exp, \x -> 10.0 * x - 3.0] > > :t funlist funlist :: Floating a => [a -> a] > funlist > (funlist !! 0) 0 0.0 > (funlist !! 0) (pi / 2.0) 1.0 > > (funlist !! 3) 10.0 97.0 > (funlist !! 3) 4.0 37.0 > -- Apply all functions to a single arguments: -- > map (\f -> f 4.0) funlist [-0.7568024953079282,-0.6536436208636119,54.598150033144236,37.0] > > let funlist2 = [\x -> 2.0 * x, (*3.0), (+10.0)] ;; > > map (\f -> f 4.0) funlist2 [8.0,12.0,14.0] > -- Functions can be generated at run-time. -- -- > let flist = map (*) [1, 2, 3, 4] > :t flist flist :: Num a => [a -> a] > > map (\f -> f 3) flist [3,6,9,12] >
Example: Haskell functions stored in a Map (aka dictionary or hash table)
import qualified Data.Map as M > :t M.fromList M.fromList :: Ord k => [(k, a)] -> M.Map k a > :{ dispatchTable = M.fromList [("sin", sin) ,("cos", cos) ,("exp", exp) ,("myfun", \x -> 10.5 * x - 3.0) ] :} > M.keys dispatchTable ["cos","exp","myfun","sin"] > > :t M.lookup "sin" dispatchTable M.lookup "sin" dispatchTable :: Floating a => Maybe (a -> a) > > fmap (\f -> f 1.0) (M.lookup "sin" dispatchTable) Just 0.8414709848078965 > > fmap (\f -> f 1.0) (M.lookup "cos" dispatchTable) Just 0.5403023058681398 > fmap (\f -> f 1.0) (M.lookup "exp" dispatchTable) Just 2.718281828459045 > > fmap (\f -> f 1.0) (M.lookup "notfound" dispatchTable) Nothing :{ applyFun dict key x = case M.lookup key dict of Just f -> Just (f x) Nothing -> Nothing :} > :t applyFun applyFun :: Ord k => M.Map k (t -> a) -> k -> t -> Maybe a > > applyFun dispatchTable "sin" 2.0 Just 0.9092974268256817 > applyFun dispatchTable "sin" 0.0 Just 0.0 > applyFun dispatchTable "sisadn" 0.0 Nothing > > let dispatchFun = applyFun dispatchTable > dispatchFun "sin" 3.1415 Just 9.265358966049026e-5 > dispatchFun "cos" 3.1415 Just (-0.9999999957076562) > > dispatchFun "myfun" 2.30 Just 21.15 > :{ applyHmap dict x = M.fromList $ map (\ (k, fn) -> (k, fn x)) $ zip (M.keys dict) (M.elems dict) :} > :t applyHmap applyHmap :: Ord k => M.Map k (t -> a) -> t -> M.Map k a > > applyHmap dispatchTable 2.0 fromList [("cos",-0.4161468365471424),("exp",7.38905609893065),("myfun",18.0),("sin",0.9092974268256817)] > -- Formatted for better display -- > map (applyHmap dispatchTable) [1.0, 2.0, 3.0, 4.0] [fromList [("cos",0.5403023058681398),("exp",2.718281828459045),("myfun",7.5),("sin",0.8414709848078965)], fromList [("cos",-0.4161468365471424),("exp",7.38905609893065),("myfun",18.0),("sin",0.9092974268256817)], fromList [("cos",-0.9899924966004454),("exp",20.085536923187668),("myfun",28.5),("sin",0.1411200080598672)], fromList [("cos",-0.6536436208636119),("exp",54.598150033144236),("myfun",39.0),("sin",-0.7568024953079282)]]
See also:
Many examples of first class functions in several languages.
1.3 Pure Functions
Pure functions:
- Are functions without side effects, like mathematical functions.
- For the same input the functions always returns the same output.
- The result of any function call is fully determined by its arguments.
- Pure functions don't rely on global variable and don't have internal states.
- They don't do IO, i.e .:. don't print, don't write a file …
- Pure functions are stateless
- Pure functions are deterministic
Why Pure Functions:
- Composability, one function can be connected to another.
- Can run in parallel, multi-threading, multi-core, GPU and distributed systems.
- Better debugging and testing.
- Predictability
Example of pure functions
def min(x, y): if x < y: return x else: return y
Example of impure function
- Impure functions doesn't have always the same output for the same
- Impure functions does IO or has Hidden State or Global Variables
exponent = 2 def powers(L): for i in range(len(L)): L[i] = L[i]**exponent return L
The function min is pure. It always produces the same result given the same inputs and it does not affect any external variable.
The function powers is impure because it not always gives the same output for the same input, it depends on the global variable exponent:
>>> exponent = 2 >>> >>> def powers(L): ... for i in range(len(L)): ... L[i] = L[i]**exponent ... return L ... >>> powers([1, 2, 3]) [1, 4, 9] >>> exponent = 4 >>> powers([1, 2, 3]) # (It is impure since it doesn't give the same result ) [1, 16, 81] >>>
Another example, purifying an impure Language:
>>> lst = [1, 2, 3, 4] # An pure function doesn't modify its arguments. >>> # therefore lst reverse is impure >>> x = lst.reverse() >>> x >>> lst [4, 3, 2, 1] >>> lst.reverse() >>> lst [1, 2, 3, 4]
Reverse list function purified:
>>> lst = [1, 2, 3, 4] >>> >>> def reverse(lst): ... ls = lst.copy() ... ls.reverse() ... return ls ... >>> >>> reverse(lst) [4, 3, 2, 1] >>> lst [1, 2, 3, 4] >>> reverse(lst) [4, 3, 2, 1] >>> lst [1, 2, 3, 4]
1.4 Referential Transparency
Referential Transparency means that any sub-expression can be replaced by its value within an expression at any time without changing the evaluation of the whole expression. This property is a characteristic of mathematical expressions that allows program transformation, program manipulation and equational reasoning. It can be basically be stated as "replace equals by equals".
If there is referential transparency the expression below is valid:
f(x) + f(x) = 2 * f(x)
The function f is referentially transparent only if it is a pure function. The application of the function can be replaced by its value without change the meaning of the expression and it yields always the same result for the same input.
Referential transparency is only possible in the absence of side-effects. Haskell is one the few language which is referencially transparent owing to the fact that it enforces purity.
Benefits:
- Program transformation
- Equational reasoning
- Every expression can replaced by its value.
- Reasoning about the result of a function can be done by replacing its definition at the place of the application regardless of the context.
- Evaluation order doesn't matter.
- More opportunities for compiler optimization
- Computations can be safely distributed over multiple processors/threads.
- Previous evaluated expressions can be memoized.
- Programs with referential transparency can be easier to reason about its behavior due to the reader does not have to think about the side-effects like global states, internal states and IO.
- Help change the code without breaking it, easier refactoring.
Example: referential transparency in Python. Note: Python as ML variants and Scheme doesn't enforce it.
>>> def square (x): ... return x * x ... >>> >>> square (3) + square (3) 18 >>> 2 * square (3) 18 >>> square (3) + square (3) == 2 * square (3) True >>> >>> x = square (3) >>> x 9 >>> x + x == 2 * square (3) True
Example:violation of referential transparency or referential opacity due to global state side-effect in Python.
state = 1 def f(x): global state state = state + 1 return x + state >>> f(2) 4 >>> f(2) 5 >>> 2 * f(2) 12 >>> # Resetting the world: # >>> state = 1 >>> >>> f(2) + f(2) == 2 * f(2) False >>> >>> import random >>> >>> random.random() + random.random () == 2 * random.random() False >>> >>> state = 0 >>> def counter (): ... global state ... state = state + 1 ... return state ... >>> counter () + counter () == 2 * counter () False >>> counter () 4 >>> counter () 5 >>>
References:
- Arrays, Functional Languages, and Parallel Systems - Google Books
- Hudak P. Evolution, and Application of Functional Programming Languages. Available at http://www.utdallas.edu/~kXh060100/cs6301fa15/p359-hudak.pdf
- Input/Output in Functional. Languages. Using Algebraic Union Types.. Available at http://essay-test.utsp.utwente.nl/57287/1/scriptie_Rorije.pdf
- Clarify Your Code in the Functional Style
- http://mccarthy.cs.iit.edu/cs440/videos/state-4up.pdf
- http://www.macs.hw.ac.uk/~hwloidl/Courses/F21DP/gph_milan15_handout.pdf
- Referential transparency - HaskellWiki
- CS 340 - Lecture 18: Functional Programming in Scala
- Lecture 14: ML, Deep/Shallow Access, Referential Transparency
- functional programming - What is referential transparency? - Programmers Stack Exchange
- Functional programming ruby mty
1.5 Closure
Closure is a function that remembers the environment at which it was created.
>>> x = 10 # The function adder remembers the environment at which it was created # it remembers the value of x # def make_adder(x): def adder(y): return x + y return adder >>> add5 = make_adder(5) >>> add10 = make_adder(10) >>> >>> add5(4) 9 >>> list(map(add5, [1, 2, 3, 4, 5])) [6, 7, 8, 9, 10] >>> x 10 >>> >>> list(map(add10, [1, 2, 3, 4, 5])) [11, 12, 13, 14, 15] # def make_printer(msg): def printer(): print(msg) return printer >>> p1 = make_printer ("Hello world") >>> p2 = make_printer ("FP programming Rocks!!") >>> >>> p1() Hello world >>> p2() FP p # Mutable state with closure idx = 100 def make_counter(): idx = -1 def _(): nonlocal idx idx = idx + 1 return idx return _ >>> idx = 100 >>> counter1 = make_counter() >>> counter1() 0 >>> counter1() 1 >>> counter1() 2 >>> counter1() 3 >>> idx 100 >>> counter2 = make_counter () >>> counter2() 0 >>> counter2() 1 >>> counter2() 2 >>> counter1() 5 >>> >>> del make_counter >>> make_counter Traceback (most recent call last): File "<stdin>", line 1, in <module> NameError: name 'make_counter' is not defined >>> >>> counter1() 6 >>> counter1() 7
Example of closure in Clojure:
(defn make-adder [x] (fn [y] (+ x y))) user=> (def add5 (make-adder 5)) #'user/add5 user=> user=> (def add10 (make-adder 10)) #'user/add10 user=> user=> (add5 10) 15 user=> (add10 20) 30 user=> (map (juxt add5 add10) [1 2 3 4 5 6]) ([6 11] [7 12] [8 13] [9 14] [10 15] [11 16]) user=> (defn make-printer [message] (fn [] (println message))) user=> (def printer-1 (make-printer "Hello world")) #'user/printer-1 user=> user=> (def printer-2 (make-printer "Hola Mundo")) #'user/printer-2 user=> user=> (printer-1) Hello world nil user=> (printer-2) Hola Mundo nil user=>
Example of closure in F# (F sharp):
let make_adder x = fun y -> x + y val make_adder : x:int -> y:int -> int > let add5 = make_adder 5 ;; val add5 : (int -> int) > let add10 = make_adder 10 ;; val add10 : (int -> int) > add5 20 ;; val it : int = 25 > - add10 30 ;; val it : int = 40 > - List.map add5 [1 ; 2; 3; 4; 5; 6] ;; val it : int list = [6; 7; 8; 9; 10; 11] > // As F# have currying like OCaml and Haskell // it could be also be done as // - let make_adder x y = x + y ;; val make_adder : x:int -> y:int -> int > let add10 = make_adder 10 ;; val add10 : (int -> int) > add10 20 ;; val it : int = 30 >
1.6 Currying and Partial Application
1.6.1 Currying
1.6.1.1 Overview
Currying is the decomposition of a function of multiples arguments in a chained sequence of functions of a single argument. The name currying comes from the mathematician Haskell Curry who developed the concept of curried functions. Curried functions can take one argument at a time and a uncurried function must have all arguments passed at once.
Let a function f(x, y) = 10*x - 3*y
which is uncurryied. This
function can only take two arguments at once.
This function can be rewritten in a curried form as:
f(x)(y) = 10*x - 3*y
By applying it to a value of x = 4 creates a function with parameter y:
- g(y) = f(4) = 10*4 - 3*y
- g(3) = f(4)(3) = 10*4 - 3*3 = 31
f (x, y) = 10*x - 3*y f (4, 3) = 10* 4 - 3*3 = 40 - 9 = 31 f (4, 3) = 31 In the curried form becomes: g(x) = (x -> y -> 10 * x - 3*y) To evaluate f(4, 3): h(y) = f(4) = (x -> y -> 10 * x - 3*y) 4 -- x = 4 = ( y -> 10 * 4 - 3*y ) = y -> 40 - 3*y h(3) = (y -> 40 - 3*y) 3 = 40 - 3*3 = 31 Or: (x -> y -> 10 * x - 3*y) 4 3 = (x -> (y -> 10 * x - 3*y)) 4 3 = ((x -> (y -> 10 * x - 3*y)) 4) 3 = (y -> 10 * 4 - 3 * y) 3 = 10 * 4 - 3 * 3 = 31
The same function h(y) can be reused: applied to other arguments, used in mapping, filtering and another higher order functions.
Ex1 h(y) = (y -> 40 - 3*y) h(10) = 40 - 3*10 = 40 - 30 = 10 Ex2 map(h, [2, 3, 4]) = [h 2, h 3, h 4] = [(y -> 40 - 3*y) 2, (y -> 40 - 3*y) 3, (y -> 40 - 3*y) 4] = [34, 31, 28]
1.6.1.2 Example in Haskell GHCI
In Haskell, Standard ML, OCaml and F# all functions are curried by default and in most of programming languages they are uncurried by default.
Example: Curried functions in Haskell.
> let f x y = 10 * x - 3 * y > :t f f :: Num a => a -> a -> a > > f 4 3 31 --- Fix the value of x = 4 --> h(y) = f(x=4) = 10 * 4 - 3 * y -- = 40 - 3 * y --- > let h_y = f 4 > :t h_y h_y :: Integer -> Integer > > h_y 3 31 {- 34 = h_y 2 = 40 - 3*2 = 34 31 = h_y 3 = 40 - 3*3 = 31 28 = h_y 4 = 40 - 3*4 = 28 -} > map h_y [2, 3, 4] [34,31,28] > > -- It is evaluated as: > ((f 4) 3) 31 > {- The function f can be also seen in this way -} > let f' = \x -> \y -> 10 * x - 3 * y > > :t f' f' :: Integer -> Integer -> Integer > > f' 4 3 31 > > (f' 4 ) 3 31 > > let h__x_is_4_of_y = f' 4 > h__x_is_4_of_y 3 31 > {- (\x -> \y -> 10 * x - 3 * y) 4 3 = (\x -> (\y -> 10 * x - 3 * y) 4) 3 = (\y -> 10 * 4 - 3 * y) 3 = (10 * 4 - 3 * 3) = 40 - 9 = 31 -} > (\x -> \y -> 10 * x - 3 * y) 4 3 31 > > ((\x -> (\y -> 10 * x - 3 * y)) 4) 3 31 > {- Curried functions are suitable for composition, pipelining (F#, OCaml with the |> operator), mapping/ filtering operations, and to create new function from previous defined increasing code reuse. -} > map (f 4) [2, 3, 4] [34,31,28] > > map ((\x -> \y -> 10 * x - 3 * y) 4) [2, 3, 4] [34,31,28] > > -- ----------------- > let f_of_x_y_z x y z = 10 * x + 3 * y + 4 * z > > :t f_of_x_y_z f_of_x_y_z :: Num a => a -> a -> a -> a > f_of_x_y_z 2 3 5 49 > > let g_of_y_z = f_of_x_y_z 2 > :t g_of_y_z g_of_y_z :: Integer -> Integer -> Integer > > g_of_y_z 3 5 49 > > let h_of_z = g_of_y_z 3 > :t h_of_z h_of_z :: Integer -> Integer > > h_of_z 5 49 > > -- So it is evaluated as > (((f_of_x_y_z 2) 3) 5) 49 >
Uncurried functions can also be defined in Haskell.
let f (x, y) = 10 * x - 3 * y Prelude> :t f f :: Num a => (a, a) -> a Prelude> {- | Uncurried function cannot be applied to one argument at a time -} Prelude> f 3 5 <interactive>:9:1: error: • Non type-variable argument in the constraint: Num (t -> t1, t -> t1) (Use FlexibleContexts to permit this) • When checking the inferred type it :: forall t t1. (Num (t -> t1, t -> t1), Num (t -> t1), Num t) => t1 Prelude> Prelude> f(3, 4) 18 Prelude> f(3, 1) 27 Prelude> f(3, 2) 24 Prelude> f(3, 5) 15 Prelude> map f [(1, 2), (3, 4), (5, 6), (7, 8)] [4,18,32,46] Prelude>
1.6.1.3 Example in Ocaml and F#
# let f x y = 10 * x - 3 * y ;; val f : int -> int -> int = <fun> # f 4 3 ;; - : int = 31 # f 4 ;; - : int -> int = <fun> # (f 4) 3 ;; - : int = 31 # # let h_y = f 4 ;; val h_y : int -> int = <fun> # h_y 3 ;; - : int = 31 # # List.map h_y [2; 3; 4] ;; - : int list = [34; 31; 28] # # List.map (f 4) [2; 3; 4] ;; - : int list = [34; 31; 28] # let f' = fun x -> fun y -> 10 * x - 3 * y ;; val f' : int -> int -> int = <fun> # (f' 4) 3 ;; - : int = 31 # (fun x -> fun y -> 10 * x - 3 * y) 4 3 ;; - : int = 31 # # List.map ((fun x -> fun y -> 10 * x - 3 * y) 4) [2; 3; 4] ;; - : int list = [34; 31; 28]
1.6.1.4 Example in Python 3
# In Python, the functions are not curried by default as in Haskell, # Standard ML, OCaml and F# # >>> def f(x, y): return 10 * x - 3*y >>> f(4, 3) 31 # However the user can create the curried form of the function f: >>> curried_f = lambda x: lambda y: 10*x - 3*y >>> curried_f(4) <function __main__.<lambda>.<locals>.<lambda>> >>> curried_f(4)(3) 31 >>> h_y = curried_f(4) # x = 4 constant >>> h_y(3) 31 >>> h_y(5) 25 >>> mapl = lambda f_x, xs: list(map(f_x, xs)) >>> mapl(h_y, [2, 3, 4]) [34, 31, 28] # Or >>> mapl(curried_f(4), [2, 3, 4]) [34, 31, 28] # Without currying the mapping would be: >>> mapl(lambda y: f(4, y), [2, 3, 4]) [34, 31, 28] ######################################## >> f_of_x_y_z = lambda x, y, z: 10 * x + 3 * y + 4 * z ## Curried form: >>> curried_f_of_x_y_z = lambda x: lambda y: lambda z: 10 * x + 3 * y + 4 * z >>> f_of_x_y_z (2, 3, 5) 49 >>> curried_f_of_x_y_z (2)(3)(5) 49 >>> g_of_y_z = curried_f_of_x_y_z(2) >>> g_of_y_z <function __main__.<lambda>.<locals>.<lambda>> >>> g_of_y_z (3)(5) 49 >>> h_of_z = g_of_y_z(3) >>> h_of_z <function __main__.<lambda>.<locals>.<lambda>.<locals>.<lambda>> >>> h_of_z(5) 49
1.6.1.5 Example in Scala
The function f(x, y) = 10 * x - 3 * y
is defined in a uncurried form.
def f(x: Int, y: Int) = 10 * x - 3 * y scala> f(3, 4) res0: Int = 18 scala> f(3) <console>:13: error: not enough arguments for method f: (x: Int, y: Int)Int. Unspecified value parameter y. f(3) scala> List(1, 2, 3, 4).map( y => f(4, y)) res5: List[Int] = List(37, 34, 31, 28)
Scala provides a syntax that makes easier to define functions in curried form:
def f(x: Int) (y: Int) = 10 * x - 3 * y scala> f(4)(1) res14: Int = 37 scala> f(4)(2) res15: Int = 34 scala> f(4)(3) res16: Int = 31 scala> f(4)(4) res17: Int = 28 scala> List(1, 2, 3, 4).map(f(4)) res13: List[Int] = List(37, 34, 31, 28) scala> f(4) _ res11: Int => Int = <function1> scala> f _ res12: Int => (Int => Int) = <function1> scala> scala> val g = (y: Int) => f(4)(y) g: Int => Int = <function1> scala> g(3) res18: Int = 31 scala> g(4) res19:
This function in curried form could also be defned in this way:
scala> val f = (x: Int) => (y: Int) => 10 * x - 3 * y f: Int => (Int => Int) = <function1> scala> f(4)(3) res2: Int = 31 scala> f(4)(2) res3: Int = 34 scala> f(4)(5) res4: Int = 25 scala> scala> val g = f(4) g: Int => Int = <function1> scala> g(5) res5: Int = 25 scala> g(3) res6: Int = 31 scala> g(2) res7: Int = 34 scala> g(5) res8: Int = 25 scala> List(1, 2, 3, 4).map(f(4)) res9: List[Int] = List(37, 34, 31, 28) scala> List(1, 2, 3, 4).map(g) res11: List[Int] = List(37, 34, 31, 28)
1.6.2 Partial Application
A function of multiple arguments is converted into a new function that takes fewer arguments, some arguments are supplied and returns function with signature consisting of remaining arguments. Partially applied functions must not be confused with currying.
Example in Python:
>>> from functools import partial >>> def f(x, y, z): return 10 * x + 3 * y + 4 * z >>> f(2, 3, 5) 49 >>> f_yz = partial(f, 2) # x = 2 >>> f_yz(3, 5) 49 >>> f_z = partial(f_yz, 3) >>> f_z(5) 49 >>> partial(f, 2, 3)(5) 49 >>> list(map(partial(f, 2, 3), [2, 3, 5])) [37, 41, 49] # # Alternative implementation of partial # def partial(f, *xs): return lambda x: f( * (tuple(xs) + (x,))) >>> list(map(partial(f, 2, 3), [2, 3, 5])) [37, 41, 49] >>>
In languages like Haskell, Standard ML, OCaml and F# currying is similar to partial application.
Example in OCaml:
# let f x y z = 10 * x + 3 *y + 4 * z ;; val f : int -> int -> int -> int = <fun> # # (f 2 3) ;; - : int -> int = <fun> # let f_z = f 2 3 ;; val f_z : int -> int = <fun> # f_z 5 ;; - : int = 49 # (** Write (f 2 3) is the same as write (f 2)(3) *) # List.map (f 2 3) [2; 3; 5] ;; - : int list = [37; 41; 49] #
See also:
1.7 Tail Call Optimization and Tail Recursive Functions
1.7.1 Tail Call
A tail call is a function call which is the last action performed by a function.
Examples of tail calls and non tail calls:
Example 1: Tail call
def func1(x): return tail_call_function (x * 2) # It is a tail call
Example 2: Tail recursive call or tail recursive function.
def tail_recursive_call (n, acc); if n = 0: return acc return tai_recursive_acll (n - 1, n * acc) # Tail recursive call, the # function call is the last # thing the function does.
Example 3: Non tail call
def non_tail_call_function(x): return 1 + non_tail_call_function (x + 3)
1.7.2 Tail Call Optimization
Tail call optimization - TCO. (aka. tail call elimination - TCE or tail recursion elimination - TRE) is a optimization that replaces calls in tail positions with jumps which guarantees that loops implemented using recursion are executed in constant stack space. {Schinz M. and Odersky M. - 2001}
Without tail call optimization each recursive call creates a new stack frame by growing the execution stack. Eventually the stack runs out of space and the program has to stop. To support iteration by recursion functional languages need tail call optimization. {Schwaighofer A. 2009} 1
If the language doesn't support TCO it is not possible to perform recursion safely. A big number of calls will lead to a stack overflow exception and the program will crash unexpectedly.
Sometimes non tail recursive functions can be changed to tail recursive by adding a new function with extra parameters (accumulators) to store partial results (state).
Languages with TCO support:
- Scheme
- Common Lisp
- Haskell
- Ocaml
- F# (F sharp)
- C# (C sharp)
- Scala
- Erlang
Languages without TCO support:
1.7.3 Summary
- To perform recursion safely a language must support TCO - Tail Call Optimization.
- Even if there is TCO support a non tail recursive function can lead to an unexpected stack overflow.
- Recursion allow greater expressiveness and many algorithms are better expressed with recursion.
- Recursion must be replaced by loops constructs in languages that doesn't support TCO.
1.7.4 Examples
Example of non tail recursive function in Scheme (GNU Guile):
(define (factorial n) (if (or (= n 0) (= n 1)) 1 (* n (factorial (- n 1))))) > (factorial 10) $1 = 3628800 > ;; For a very big number of iterations, non tail recursive functions ;; will cause a stack overflow. ;; > (factorial 20000000) warnings can be silenced by the --no-warnings (-n) option Aborted (core dumped) ;; ;; This execution requires 5 stack frames ;; ;; (factorial 5) ;; (* 5 (factorial 4)) ;; (* 5 (* 4 (factorial 3))) ;; (* 5 (* 4 (3 * (factorial 2)))) ;; (* 5 (* 4 (* 3 (factorial 2)))) ;; (* 5 (* 4 (* 3 (* 2 (factorial 1))))) ;; ;; (* 5 (* 4 (* 3 (* 2 1)))) ;; (* 5 (* 4 (* 3 2))) ;; (* 5 (* 4 6)) ;; (* 5 24) ;; 120 ;; ;; ;; ;; > ,trace (factorial 5) trace: | (#<procedure 99450c0> #(#<directory (guile-user) 95c3630> …)) trace: | #(#<directory (guile-user) 95c3630> factorial) trace: (#<procedure 9953350 at <current input>:8:7 ()>) trace: (factorial 5) trace: | (factorial 4) trace: | | (factorial 3) trace: | | | (factorial 2) trace: | | | | (factorial 1) trace: | | | | 1 trace: | | | 2 trace: | | 6 trace: | 24 trace: 120 > ;; ;; It requires 10 stack frames ;; ;; > ,trace (factorial 10) trace: | (#<procedure 985cbd0> #(#<directory (guile-user) 95c3630> …)) trace: | #(#<directory (guile-user) 95c3630> factorial) trace: (#<procedure 9880800 at <current input>:6:7 ()>) trace: (factorial 10) trace: | (factorial 9) trace: | | (factorial 8) trace: | | | (factorial 7) trace: | | | | (factorial 6) trace: | | | | | (factorial 5) trace: | | | | | | (factorial 4) trace: | | | | | | | (factorial 3) trace: | | | | | | | | (factorial 2) trace: | | | | | | | | | (factorial 1) trace: | | | | | | | | | 1 trace: | | | | | | | | 2 trace: | | | | | | | 6 trace: | | | | | | 24 trace: | | | | | 120 trace: | | | | 720 trace: | | | 5040 trace: | | 40320 trace: | 362880 trace: 3628800 >
This function can be converted to a tail recursive function by using an accumulator:
(define (factorial-aux n acc) (if (or (= n 0) (= n 1)) acc (factorial-aux (- n 1) (* n acc)))) > (factorial-aux 6 1) $1 = 720 > ,trace (factorial-aux 6 1) trace: | (#<procedure 9becf10> #(#<directory (guile-user) 984c630> …)) trace: | #(#<directory (guile-user) 984c630> factorial-aux) trace: (#<procedure 9bec320 at <current input>:26:7 ()>) trace: (factorial-aux 6 1) trace: (factorial-aux 5 6) trace: (factorial-aux 4 30) trace: (factorial-aux 3 120) trace: (factorial-aux 2 360) trace: (factorial-aux 1 720) trace: 720 scheme@(guile-user)> > (define (factorial2 n) (factorial-aux n 1)) scheme@(guile-user)> (factorial2 5) $3 = 120 ;; This function could also be implemented in this way: ;; ;; (define (factorial3 n) (define (factorial-aux n acc) (if (or (= n 0) (= n 1)) acc (factorial-aux (- n 1) (* n acc)))) (factorial-aux n 1)) > (factorial3 6) $4 = 720 > (factorial3 5) $5 = 120
Example: Summation of a range of numbers:
;; Non tail recursive function: ;; (define (sum-ints a b) (if (> a b) 0 (+ a (sum-ints (+ a 1) b)))) ;; ;; Using the trace command is possible to notice the growing amount of ;; stack frame In this case it requires 11 stack frames. > ,trace (sum-ints 1 10) trace: | (#<procedure 9c42420> #(#<directory (guile-user) 984c630> …)) trace: | #(#<directory (guile-user) 984c630> sum-ints) trace: (#<procedure 9c4b8c0 at <current input>:56:7 ()>) trace: (sum-ints 1 10) trace: | (sum-ints 2 10) trace: | | (sum-ints 3 10) trace: | | | (sum-ints 4 10) trace: | | | | (sum-ints 5 10) trace: | | | | | (sum-ints 6 10) trace: | | | | | | (sum-ints 7 10) trace: | | | | | | | (sum-ints 8 10) trace: | | | | | | | | (sum-ints 9 10) trace: | | | | | | | | | (sum-ints 10 10) trace: | | | | | | | | | | (sum-ints 11 10) trace: | | | | | | | | | | 0 trace: | | | | | | | | | 10 trace: | | | | | | | | 19 trace: | | | | | | | 27 trace: | | | | | | 34 trace: | | | | | 40 trace: | | | | 45 trace: | | | 49 trace: | | 52 trace: | 54 trace: 55 ;; Stack Overflow Error ;; > (sum-ints 1 10000) > <unnamed port>:4:13: In procedure sum-ints: <unnamed port>:4:13: Throw to key `vm-error' with args `(vm-run "VM: Stack overflow" ())'. ;; ;; Safe summation ;; (define (sum-ints-aux a b acc) (if (> a b) acc (sum-ints-aux (+ a 1) b (+ a acc)))) (define (sum-ints-aux a b acc) (if (> a b) acc (sum-ints-aux (+ a 1) b (+ a acc)))) > (sum-ints-aux 1 10 0) $4 = 55 > > (sum-ints-aux 1 10000 0) $6 = 50005000 ;; ;; It uses only one stack frame each call ;; > ,trace (sum-ints-aux 1 10 0) trace: | (#<procedure 985a270> #(#<directory (guile-user) 93fd630> …)) trace: | #(#<directory (guile-user) 93fd630> sum-ints-aux) trace: (#<procedure 98646a0 at <current input>:31:7 ()>) trace: (sum-ints-aux 1 10 0) trace: (sum-ints-aux 2 10 1) trace: (sum-ints-aux 3 10 3) trace: (sum-ints-aux 4 10 6) trace: (sum-ints-aux 5 10 10) trace: (sum-ints-aux 6 10 15) trace: (sum-ints-aux 7 10 21) trace: (sum-ints-aux 8 10 28) trace: (sum-ints-aux 9 10 36) trace: (sum-ints-aux 10 10 45) trace: (sum-ints-aux 11 10 55) trace: 55 > ;; It can also be implemented in this way: ;; (define (sum-ints-safe a b) (define (sum-ints-aux a b acc) (if (> a b) acc (sum-ints-aux (+ a 1) b (+ a acc)))) (sum-ints-aux a b 0)) > scheme@(guile-user)> (sum-ints-safe 1 1000) $2 = 500500 > (sum-ints-safe 1 10000) $7 = 50005000 > (sum-ints-safe 1 100000) $8 = 5000050000 scheme@(guile-user)>
Example: of summation in a language without TCO: python
def sum_ints_aux (a, b, acc): if a > b: return acc else: return sum_ints_aux (a + 1, b, a + acc) # Until now works >>> >>> sum_ints_aux(1, 10, 0) 55 >>> sum_ints_aux(1, 100, 0) 5050 # Now it is going to fail: Stack Overflow! >>> sum_ints_aux(1, 1000, 0) Traceback (most recent call last): File "<stdin>", line 1, in <module> File "<stdin>", line 5, in sum_ints_aux File "<stdin>", line 5, in sum_ints_aux ... File "<stdin>", line 5, in sum_ints_aux File "<stdin>", line 2, in sum_ints_aux RuntimeError: maximum recursion depth exceeded in comparison >>> # Solution: Turn the recursion into a loop: # def sum_ints (a, b): x = a acc = 0 while x < b: x = x + 1 acc = acc + x return acc + 1 >> sum_ints (1, 1000) 500500 >> sum_ints (1, 10000) 50005000
Example: Implementing map with tail recursion.
(define (map2 f xs) (if (null? xs) '() (cons (f (car xs)) (map2 f (cdr xs))))) (define (inc x) (+ x 1)) ;; It will eventually lead to an stack overflow for a big list. ;; > ,trace (map2 inc '(1 2 3)) trace: | (#<procedure 9e14500> #(#<directory (guile-user) 984c630> …)) trace: | #(#<directory (guile-user) 984c630> map2 inc (1 2 3)) trace: (#<procedure 9e48360 at <current input>:109:7 ()>) trace: (map2 #<procedure inc (x)> (1 2 3)) trace: | (inc 1) trace: | 2 trace: | (map2 #<procedure inc (x)> (2 3)) trace: | | (inc 2) trace: | | 3 trace: | | (map2 #<procedure inc (x)> (3)) trace: | | | (inc 3) trace: | | | 4 trace: | | | (map2 #<procedure inc (x)> ()) trace: | | | () trace: | | (4) trace: | (3 4) trace: (2 3 4) ,trace (map2 inc '(1 2 3 4 5 6 7 8 9)) trace: | (#<procedure 9cdcb00> #(#<directory (guile-user) 984c630> …)) trace: | #(#<directory (guile-user) 984c630> map2 inc (1 2 3 4 5 6 …)) trace: (#<procedure 9ceebf0 at <current input>:104:7 ()>) trace: (map2 #<procedure inc (x)> (1 2 3 4 5 6 7 8 9)) trace: | (inc 1) trace: | 2 trace: | (map2 #<procedure inc (x)> (2 3 4 5 6 7 8 9)) trace: | | (inc 2) trace: | | 3 trace: | | (map2 #<procedure inc (x)> (3 4 5 6 7 8 9)) trace: | | | (inc 3) trace: | | | 4 trace: | | | (map2 #<procedure inc (x)> (4 5 6 7 8 9)) trace: | | | | (inc 4) trace: | | | | 5 trace: | | | | (map2 #<procedure inc (x)> (5 6 7 8 9)) trace: | | | | | (inc 5) trace: | | | | | 6 trace: | | | | | (map2 #<procedure inc (x)> (6 7 8 9)) trace: | | | | | | (inc 6) trace: | | | | | | 7 trace: | | | | | | (map2 #<procedure inc (x)> (7 8 9)) trace: | | | | | | | (inc 7) trace: | | | | | | | 8 trace: | | | | | | | (map2 #<procedure inc (x)> (8 9)) trace: | | | | | | | | (inc 8) trace: | | | | | | | | 9 trace: | | | | | | | | (map2 #<procedure inc (x)> (9)) trace: | | | | | | | | | (inc 9) trace: | | | | | | | | | 10 trace: | | | | | | | | | (map2 #<procedure inc (x)> ()) trace: | | | | | | | | | () trace: | | | | | | | | (10) trace: | | | | | | | (9 10) trace: | | | | | | (8 9 10) trace: | | | | | (7 8 9 10) trace: | | | | (6 7 8 9 10) trace: | | | (5 6 7 8 9 10) trace: | | (4 5 6 7 8 9 10) trace: | (3 4 5 6 7 8 9 10) trace: (2 3 4 5 6 7 8 9 10) (define (map-aux f xs acc) (if (null? xs) (reverse acc) (map-aux f (cdr xs) (cons (f (car xs)) acc) ) ) ) > ,trace (map-aux inc '(1 2 3 4 5) '()) trace: | (#<procedure 9e0c420> #(#<directory (guile-user) 984c630> …)) trace: | #(#<directory (guile-user) 984c630> map-aux inc (1 2 3 4 5)) trace: (#<procedure 9e4c070 at <current input>:180:7 ()>) trace: (map-aux #<procedure inc (x)> (1 2 3 4 5) ()) trace: | (inc 1) trace: | 2 trace: (map-aux #<procedure inc (x)> (2 3 4 5) (2)) trace: | (inc 2) trace: | 3 trace: (map-aux #<procedure inc (x)> (3 4 5) (3 2)) trace: | (inc 3) trace: | 4 trace: (map-aux #<procedure inc (x)> (4 5) (4 3 2)) trace: | (inc 4) trace: | 5 trace: (map-aux #<procedure inc (x)> (5) (5 4 3 2)) trace: | (inc 5) trace: | 6 trace: (map-aux #<procedure inc (x)> () (6 5 4 3 2)) trace: (reverse (6 5 4 3 2)) trace: (2 3 4 5 6) ;; Finally ;; (define (map-safe f xs) (map-aux f xs '())) > (map-safe inc '(1 2 3 3 4 5)) $14 = (2 3 4 4 5 6)
Example in F#:
> let inc x = x + 1 ;; val inc : x:int -> int let rec map_aux f xs acc = match xs with | [] -> List.rev acc | hd::tl -> map_aux f tl ((f hd)::acc) ;; val map_aux : f:('a -> 'b) -> xs:'a list -> acc:'b list -> 'b list > map_aux inc [1; 2; 3; 4; 5] [] ;; val it : int list = [2; 3; 4; 5; 6] let map2 f xs = map_aux f xs [] ;; val map2 : f:('a -> 'b) -> xs:'a list -> 'b list > map2 inc [1; 2; 3; 4; 5] ;; val it : int list = [2; 3; 4; 5; 6] > // map_aux without pattern matching // let rec map_aux f xs acc = if List.isEmpty xs then List.rev acc else (let hd, tl = (List.head xs, List.tail xs) in map_aux f tl ((f hd)::acc)) ;; val map_aux : f:('a -> 'b) -> xs:'a list -> acc:'b list -> 'b list > map2 inc [1; 2; 3; 4; 5] ;; val it : int list = [2; 3; 4; 5; 6] > // Another way: // // let map3 f xs = let rec map_aux f xs acc = match xs with | [] -> List.rev acc | hd::tl -> map_aux f tl ((f hd)::acc) in map_aux f xs [] ;; val map3 : f:('a -> 'b) -> xs:'a list -> 'b list > map3 inc [1; 2; 3; 4; 5; 6] ;; val it : int list = [2; 3; 4; 5; 6; 7] >
Example: Tail recursive filter function.
let rec filter_aux f xs acc = match xs with | [] -> List.rev acc | hd::tl -> if (f hd) then filter_aux f tl (hd::acc) else filter_aux f tl acc ;; val filter_aux : f:('a -> bool) -> xs:'a list -> acc:'a list -> 'a list > filter_aux (fun x -> x % 2 = 0) [1; 2; 3; 4; 5; 6; 7; 8] [] ;; val it : int list = [2; 4; 6; 8] > let filter f xs = filter_aux f xs [] ;; val filter : f:('a -> bool) -> xs:'a list -> 'a list > filter (fun x -> x % 2 = 0) [1; 2; 3; 4; 5; 6; 7; 8] ;; val it : int list = [2; 4; 6; 8] >
1.7.5 See also
- Tail call - Wikipedia, the free encyclopedia
- Optimizing Tail Call Recursion
- Trampolines in JavaScript
- Functional JavaScript – Tail Call Optimization and Trampolines | @taylodl's getting IT done
- java - Why does the JVM still not support tail-call optimization? - Stack Overflow
- Tail Recursion: Iteration in Haskell – Good Math, Bad Math
- Tail call explained
- Automatic Transformation of Iterative Loops into Recursive Methods
- The Road to Functional Programming in F# – From Imperative to Computation Expressions « Inviting Epiphany
- Optimizing List.map - Jane Street Tech Blogs
1.8 Fundamental Higher Order Functions
1.8.1 Overview
The functions map, filter and reduce (fold left) are ubiquitous in many programming languages and also the most used higher order functions.
They can be strict evaluated like in Scheme and JavaScript or lazy evaluated like in Python and Haskell.
1.8.2 Map
- Overview
The function map applies a function to each element of a sequence: list, vector, hash map or dictionary and trees.
map :: ( a -> b) -> [a] -> [b] | | |----> f :: a -> b f :: a -> b a ------------------------>>> b map f :: [a] -> [b] [a] ------------------------->>> [b]
- Map in Haskell
The function map is lazy evaluated.
> let fun1 x = 3 * x + 1 > fun1 2 7 > map fun1 [1, 2, 3] [4,7,10] > -- The sequence 1 to 1000000 is not evaluated at all, -- > take 10 (map fun1 [1..1000000]) [4,7,10,13,16,19,22,25,28,31] > take 10 (map fun1 [1..10000000000]) [4,7,10,13,16,19,22,25,28,31] > > -- -- When applied to a function without a list, it creates -- another function that operates over lists because all -- Haskell functions are curried by default. -- -- f :: (a -> b) -- map :: (a -> b) -> [a] -> [b] -- -- It can be seen as: -- -- When map is applied to f, it will create the function fs -- that take list of type a and returns list of type b. -- -- map :: (a -> b) -> ([a] -> [b]) -- | | -- | |------ fs :: [a] -> [b] -- | -- -------------------- f :: a -> b -- > :t map map :: (a -> b) -> [a] -> [b] > let f x = 3 * x + 6 > :t f f :: Num a => a -> a > > map f [1, 2, 3] [9,12,15] > -- Note: let is only needed in the REPL -- > let fs = map f > :t fs fs :: [Integer] -> [Integer] > fs [1, 2, 3] [9,12,15] >
- Map in Scala
In Scala the higher order function map is encoded as a higher order method, a method that accept a function as argument. Many Scala's data structures, also known as collections, provide the method .map to apply a function to its elements.
Examples:
scala> List(1, 2, 3, 4, 5).map(x => x * 3) res0: List[Int] = List(3, 6, 9, 12, 15) scala> Array(1, 2, 3, 4, 5).map(x => x * 3) res1: Array[Int] = Array(3, 6, 9, 12, 15) // Dictionary or Hash map // scala> val dict = Map("x" -> 1, "y" -> 2, "z" -> 3) dict: scala.collection.immutable.Map[String,Int] = Map(x -> 1, y -> 2, z -> 3) scala> dict("x") res7: Int = 1 scala> dict("y") res8: Int = 2 scala> dict.map{ case (k, v) => (k, v * 3) } res9: scala.collection.immutable.Map[String,Int] = Map(x -> 3, y -> 6, z -> 9) scala> dict2("z") res10: Int = 9 scala> dict2("x") res11: Int = 3
- Map in Dynamically Typed Languages
In dynamic typed languages like Python, Clojure and Scheme the function map can take multiple arguments. In typed languages the function takes only one argument.
Map in Python:
>>> list(map (lambda a, b, c: 100 * a + 10 * b + c, [1, 2, 3, 4, 5], [8, 9, 10, 11, 12], [3, 4, 7, 8, 10])) [183, 294, 407, 518, 630] >>>
Map in Scheme:
(map (lambda (a b c) (+ (* 100 a) (* 10 b) c)) '(1 2 3 4 5) '(8 9 10 11 12) '(3 4 7 8 10)) $1 = (183 294 407 518 630)
Map in Clojure:
;; f a b c = 100 * a + 10 * b + c ;; ;; 183 = f 1 8 3 ;; 294 = f 2 9 4 ;; ... ;; 630 = f 6 3 0 ;; user=> (map (fn [a b c] (+ (* 100 a) (* 10 b) c)) [1 2 3 4 5] [8 9 10 11 12] [3 4 7 8 10]) (183 294 407 518 630) user=> ;; ;; The Clojure map is Polymorphic it can be applied to any collection ;; of seq abstraction like lists, vectors and hash maps. ;; ;; Map applied to a list ;; user=> (map inc '(1 2 3 4 5 6)) (2 3 4 5 6 7) user=> ;; Map applied to a vector ;; user=> (map inc [1 2 3 4 5 6]) (2 3 4 5 6 7) user=> ;; Map applied to a hash map ;; user=> (map identity {:a 10 :b 20 :c "hello world"}) ([:a 10] [:b 20] [:c "hello world"]) user=> ;; The function mapv is similar to map, but returns a vector: ;; user=> (mapv identity {:a 10 :b 20 :c "hello world"}) [[:a 10] [:b 20] [:c "hello world"]] user=> ;; Clojure also has destructuring ;; user=> (map (fn [[[a b] c]] (+ (* 100 a ) (* 10 b) c)) [[[1 2] 3] [[3 4] 5] [[1 2] 4]]) (123 345 124) user=>
- Map in Python
In Python 3 map and filter are lazy evaluated, they return a generator.
>>> def fun1 (x): return 3*x + 6 ... >>> g = map(fun1, [1, 2, 3]) >>> g <map object at 0xb6b4a76c> >>> next (g) 9 >>> next (g) 12 >>> next (g) 15 >>> next (g) Traceback (most recent call last): File "<stdin>", line 1, in <module> StopIteration >>> g <map object at 0xb6b4a76c> >>> # Force the evaluation: # >>> list(map(fun1, [1, 2, 3])) [9, 12, 15] # Strict Version of map # # s_ stands for strict map. def s_map (f, xs): return list(map(f, xs)) >>> s_map (fun1, [1, 2, 3]) [9, 12, 15] >>> # As python doesn't have tail call optimization # therefore recursion must be avoided because # a big number of function calls # can lead to stack overflow. def strict_map (f, xs): return [f (x) for x in xs] >>> strict_map (fun1, [1, 2, 3]) [9, 12, 15] >>> strict_map (fun1, range(5)) [6, 9, 12, 15, 18] >>> # Lazy map implementation: # Note: the python native map is implemented in C, so # it is faster. # def lazy_map (f, xs): for x in xs: yield x >>> g = lazy_map (fun1, [1, 2, 3]) >>> next(g) 1 >>> next(g) 2 >>> next(g) 3 >>> next(g) Traceback (most recent call last): File "<stdin>", line 1, in <module> StopIteration >>> list(lazy_map (fun1, [1, 2, 3])) [1, 2, 3] >>> # # In order for the map function work in the same way # as Haskell and ML it is must be curried. # curry2 = lambda f: lambda x: lambda y: f(x, y) # The function curry2 currify a function of two arguments # >>> strict_map_c = curry2(strict_map) >>> strict_map_c(fun1) <function <lambda>.<locals>.<lambda>.<locals>.<lambda> at 0xb6afc0bc> >>> strict_map_c(fun1)([1, 2, 3, 4]) [9, 12, 15, 18] >>> >>> fun1_xs = strict_map_c(fun1) >>> fun1_xs ([1, 2, 3, 4]) [9, 12, 15, 18] >>>
1.8.3 Filter
Python
;;; Filter returns by default a >>> g = filter (lambda x: x > 10, [1, 20, 3, 40, 4, 14, 8]) >>> g <filter object at 0xb6b4a58c> >>> [x for x in g] [20, 40, 14] >>> [x for x in g] [] >>> list(filter (lambda x: x > 10, [1, 20, 3, 40, 4, 14, 8])) [20, 40, 14] >>> # Strict Version of the filter function # >>> _filter = lambda f, xs: list(filter(f, xs)) >>> >>> _filter (lambda x: x > 10, [1, 20, 3, 40, 4, 14, 8]) [20, 40, 14] >>> # Filter implementation without recursion: # def strict_filter (f, xs): result = [] for x in xs: if f(x): result.append(x) return result def lazy_filter (f, xs): for x in xs: if f(x): yield x >>> strict_filter (lambda x: x > 10, [1, 20, 3, 40, 4, 14, 8]) [20, 40, 14] >>> lazy_filter (lambda x: x > 10, [1, 20, 3, 40, 4, 14, 8]) <generator object lazy_filter at 0xb6b0f1bc> >>> g = lazy_filter (lambda x: x > 10, [1, 20, 3, 40, 4, 14, 8]) >>> g <generator object lazy_filter at 0xb6b0f194> >>> next(g) 20 >>> next(g) 40 >>> next(g) 14 >>> next(g) Traceback (most recent call last): File "<stdin>", line 1, in <module> StopIteration >>> >>> list(lazy_filter (lambda x: x > 10, [1, 20, 3, 40, 4, 14, 8])) [20, 40, 14] >>>
1.8.4 Reduce or Fold
1.8.4.1 Overview
The function fold or reduce is one of the most important higher order functions as it can be used to implement many other higher order functions, eliminate recursion and operate over many data structures or collections.
Fold Left
The function fold left is tail recursive, whereas the function fold right is not. This functions is also known as reduce or inject (in Ruby). The function fold left is often called just fold like in F# or reduce (Python, Javascript, Clojure) and also Inject (Ruby).
foldl :: (State -> x -> State) -> State -> [x] -> State
foldl (f :: S -> x -> S) S [x]
Sn = foldl f S0 [x0, x1, x2, x3 ... xn-1] S1 = f S0 x0 S2 = f S1 x1 = f (f S0 x0) x1 S3 = f S2 x2 = f (f (f S0 x0) x1) x2 S4 = f S3 x3 = f (f (f (f S0 x0) x1) x2) x3 ... Sn-1 = f Sn-2 Xn-2 = ... Sn = f Sn-1 Xn-1 = f ...(f (f (f (f S0 x0) x1) x2) x3 ... xn ;;; -> Result
Fold Right
foldr :: (x -> acc -> acc) -> acc -> [x] -> acc
S1 = f xn-1 S0 S2 = f xn-2 S1 = f xn-2 (f xn-1 S0) S3 = f xn-3 S2 = f xn-3 (f xn-2 (f xn-1 S0)) S4 = f xn-4 S3 = f xn-4 (f xn-3 (f xn-2 (f xn-1 S0))) .... Sn-1 = f x1 Sn-2 = ... Sn = f x0 Sn-1 = f x0 (f x1 ... (f xn-2 (f xn-1 S0)))
1.8.4.2 Haskell
See also:
- Fold (higher-order function) - Wikipedia, the free encyclopedia)
- A tutorial on the universality and expressiveness of fold. GRAHAM HUTTON
- Haskell unit 6: The higher-order fold functions | Antoni Diller
Fold Left:
foldl :: (acc -> x -> acc) -> acc -> [x] -> acc | | | | | | | |---> Returns the accumulated | | | value | | |----- xs | | | | Inital Value of accumulator | |--- acc0 | |----------------- f :: acc -> x -> acc | |--- Element of list foldl :: (b -> a -> b) -> b -> [a] -> b foldl f z [] = z foldl f z (x:xs) = foldl f (f z x) xs
> :t foldl foldl :: (a -> b -> a) -> a -> [b] -> a > > foldl (\acc x -> 10 * acc + x) 0 [1, 2, 3, 4, 5] 12345 >
It is equivalent to:
> let f acc x = 10 * acc + x > > (f 0 1) 1 > (f (f 0 1) 2) 12 > (f (f (f 0 1) 2) 3) 123 > > (f (f (f (f 0 1) 2) 3) 4) 1234 > (f (f (f (f (f 0 1) 2) 3) 4) 5) 12345 >
Evaluation of Fold left:
> foldl (\acc x -> 10 * acc + x ) 0 [1, 2, 3, 4, 5] 12345 S0 = 0 f = \acc x -> 10 * acc + x x acc S1 = f S0 x0 = f 0 1 = 10 * 0 + 1 = 1 S2 = f S1 x1 = f 10 2 = 10 * 1 + 2 = 12 S3 = f S2 x2 = f 12 3 = 10 * 12 + 3 = 123 S4 = f S3 x3 = f 123 4 = 10 * 123 + 4 = 1234 S5 = f S3 x3 = f 123 4 = 10 * 1234 + 5 = 12345
Fold right
foldr :: (x -> acc -> acc) -> acc -> [x] -> acc foldr :: (a -> b -> b) -> b -> [a] -> b foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs)
> foldr (\x acc -> 10 * acc + x) 0 [1, 2, 3, 4, 5] 54321 > (f 0 5) 5 > (f (f 0 5) 4) 54 > (f (f (f 0 5) 4) 3) 543 > (f (f (f (f 0 5) 4) 3) 2) 5432 > (f (f (f (f (f 0 5) 4) 3) 2) 1) 54321 > -- -- Derive fold_right from foldl (fold left) -- > let fold_right f acc xs = foldl (\x acc -> f acc x) acc (reverse xs) > > :t fold_right fold_right :: (b -> a -> a) -> a -> [b] -> a > > > fold_right (\x acc -> 10 * acc + x) 0 [1, 2, 3, 4, 5] 54321 >
Evaluation of Fold Right:
Example: > foldr (\x acc -> 10 * acc + x ) 0 [1, 2, 3, 4, 5] 54321 > f = \x acc -> 10 * acc + x S0 = 0 n = 5 x acc S1 = f x4 S0 = f 5 0 = 10 * 0 + 5 = 5 S2 = f x3 S1 = f 4 5 = 10 * 5 + 4 = 54 S3 = f x2 S2 = f 3 54 = 10 * 54 + 3 = 543 S4 = f x1 S3 = f 2 543 = 10 * 543 + 2 = 5432 S5 = f x0 S4 = f 1 5432 = 10 * 5432 + 1 = 54321
1.8.4.3 F# Fsharp
// Fold left for Lists // // // List.fold (acc -> 'x -> 'acc) -> acc -> 'x list -> 'acc // - List.fold ;; val it : (('a -> 'b -> 'a) -> 'a -> 'b list -> 'a) - List.fold (fun acc x -> 10 * acc + x) 0 [1; 2; 3; 4; 5] ;; val it : int = 12345 > // Array.fold // // - Array.fold ;; val it : (('a -> 'b -> 'a) -> 'a -> 'b [] -> 'a) > - Array.fold (fun acc x -> 10 * acc + x) 0 [| 1; 2; 3; 4; 5 |] ;; val it : int = 12345 > // Fold left for Arrays
Example: Implementing Higher Order Functions and recursive functions with fold.
// Implementing fold_left for lists // let rec fold_left f xs acc = match xs with | [] -> acc | hd::tl -> fold_left f tl (f acc hd) ;; val fold_left : f:('a -> 'b -> 'a) -> xs:'b list -> acc:'a -> 'a - fold_left (fun acc x -> 10 * acc + x) [1; 2; 3; 4 ; 5] 0 ;; val it : int = 12345 > let length xs = fold_left (fun acc x -> acc + 1) xs 0 > length ["a"; "b"; "c"; "d" ] ;; val it : int = 4 > length [ ] ;; val it : int = 0 > - let sum xs = fold_left (fun acc x -> acc + x) xs 0 ;; > sum [1; 2; 3; 4; 5; 6] ;; val it : int = 21 > > let product xs = fold_left (fun acc x -> acc * x) xs 1 ;; val product : xs:int list -> int > product [1; 2; 3; 4; 5; 6] ;; val it : int = 720 > - let reverse xs = fold_left (fun acc x -> x :: acc) xs [] - ;; val reverse : xs:'a list -> 'a list > reverse [1; 2; 3; 4; 5 ] ;; val it : int list = [5; 4; 3; 2; 1] > let fold_right f xs acc = fold_left (fun acc x -> f x acc) (reverse xs) acc ;; val fold_right : f:('a -> 'b -> 'b) -> xs:'a list -> acc:'b -> 'b - fold_right (fun x acc -> 10 * acc + x) [1; 2; 3; 4; 5] 0 ;; val it : int = 54321 > // Reverse map // - let rev_map f xs = fold_left (fun acc x -> (f x)::acc) xs [] ;; val rev_map : f:('a -> 'b) -> xs:'a list -> 'b list - rev_map (fun x -> x * 2) [1; 2; 3; 4; 5; 6] ;; val it : int list = [12; 10; 8; 6; 4; 2] > - let map f xs = reverse ( fold_left (fun acc x -> (f x)::acc) xs [] ) ;; val map : f:('a -> 'b) -> xs:'a list -> 'b list - map (fun x -> x * 2) [1; 2; 3; 4; 5; 6] ;; val it : int list = [2; 4; 6; 8; 10; 12] > // Or // let rev_fold_left f xs acc = reverse (fold_left f xs acc) ;; val rev_fold_left : f:('a list -> 'b -> 'a list) -> xs:'b list -> acc:'a list -> 'a list // Map with fold left and reverse // // > let map f xs = rev_fold_left (fun acc x -> (f x)::acc) xs [] ;; val map : f:('a -> 'b) -> xs:'b list -> 'b list - map (fun x -> x * 2) [1; 2; 3; 4; 5; 6] ;; val it : int list = [2; 4; 6; 8; 10; 12] > // Map with fold right // > let map f xs = fold_right (fun x acc -> (f x)::acc) xs [] ;; val map : f:('a -> 'b) -> xs:'a list -> 'b list > map (fun x -> x * 2) [1; 2; 3; 4; 5; 6] ;; val it : int list = [2; 4; 6; 8; 10; 12] > // Filter with fold left and reverse // let filter f xs = rev_fold_left (fun acc x -> if (f x) then (x::acc) else acc) xs [] ;; val filter : f:('a -> bool) -> xs:'a list -> 'a list - filter (fun x -> x % 2 = 0) [1; 2; 3; 4; 5; 6; 7; 8; 9 ] ;; val it : int list = [2; 4; 6; 8] > // Filter with fold right // let filter f xs = fold_right (fun x acc -> if (f x) then x::acc else acc ) xs [] ;; - filter (fun x -> x % 2 = 0) [1; 2; 3; 4; 5; 6; 7; 8; 9 ] ;; val it : int list = [2; 4; 6; 8] > let take n xs = let _, result = fold_left (fun acc x -> let (c, xss) = acc in if c = 0 then (0, xss) else (c - 1, x::xss)) xs (n, []) in reverse result ;; - take ;; val it : (int -> 'a list -> 'a list) = <fun:clo@202-3> > > take 3 [1; 2; 3 ; 4; 5; 6; 7; 8] ;; val it : int list = [1; 2; 3] > - take 18 [1; 2; 3 ; 4; 5; 6; 7; 8] ;; val it : int list = [1; 2; 3; 4; 5; 6; 7; 8] > // drop with fold left // let drop n xs = let _, result = fold_left (fun acc x -> let (c, xss) = acc in if c = 0 then (0, x::xss) else (c - 1, xss)) xs (n, []) in reverse result ;; val drop : n:int -> xs:'a list -> 'a list - drop 3 [1; 2; 3 ; 4; 5; 6; 7; 8] ;; val it : int list = [4; 5; 6; 7; 8] > - drop 13 [1; 2; 3 ; 4; 5; 6; 7; 8] ;; val it : int list = [] > let take_while f xs = fold_right (fun x acc -> if (f x) then x::acc else acc ) xs [] ;; let take_while f xs = fold_right (fun x acc -> if (f x) then x::acc else match acc with | [] -> [] | _::tl -> tl ) xs [] ;; val take_while : f:('a -> bool) -> xs:'a list -> 'a list > take_while (fun x -> x < 10) [2; 8 ; 9 ; 26 ; 7; 10; 53] ;; val it : int list = [2; 8; 9] > let find f xs = fold_left (fun acc x -> if (f x) then Some x else None ) xs None ;; val find : f:('a -> bool) -> xs:'a list -> 'a option - find (fun x -> x * x > 40) [1; 2; 6; 5; 4; 8; 10; 20 ; 9 ] ;; val it : int option = Some 9 > - find (fun x -> x * x > 400) [1; 2; 6; 5; 4; 8; 10; 20 ; 9 ] ;; val it : int option = None > // Map with side-effect // let for_each f xs = fold_left (fun acc x -> f x) xs () ;; val for_each : f:('a -> unit) -> xs:'a list -> unit > for_each (fun x -> printfn "x = %d" x) [2; 3; 4; 5; 6] ;; x = 2 x = 3 x = 4 x = 5 x = 6 val it : unit = () > // Filter map - fusion / optimization // // (Eliminate intermediate data structure ) // let filter_map f_filter f_map xs = fold_right (fun x acc -> if (f_filter x) then (f_map x)::acc else acc ) xs [] ;; val filter_map : f_filter:('a -> bool) -> f_map:('a -> 'b) -> xs:'a list -> 'b list - filter_map (fun x -> x % 2 = 0) (fun x -> x + 3) [1; 5; 2; 6; 8; 7] - ;; val it : int list = [5; 9; 11] > // Without optimization - map (fun x -> x + 3) (filter (fun x -> x % 2 = 0) [1; 5; 2; 6; 8; 7]) ;; val it : int list = [5; 9; 11] > -
1.8.4.4 Scala
In Scala, this function is encoded as a higher order method common to many collections.
scala> List(1, 2, 3, 4, 5, 6).foldLeft(0)((acc, x) => 10 * acc + x) res17: Int = 123456 scala> List(1, 2, 3, 4, 5, 6).foldRight(0)((x, acc) => 10 * acc + x) res19: Int = 654321 scala> val files = new java.io.File("/").listFiles() files: Array[java.io.File] = Array(/lost+found, /boot, ...) // Count the number of files in the root / *nix, Linux directory // scala> files.foldLeft(0)((acc, x) => acc + 1) res21: Int = 22 // Dictionary Collection // scala> val dict = Map("x" -> 20.24, "y" -> 30.5, "z" -> 100.23) dict: scala.collection.immutable.Map[String,Double] = Map(x -> 20.24, y -> 30.5, z -> 100.23) /// Get the sum of hash table values /// scala> dict.foldLeft(0.0){ case (acc, (k, v)) => acc + v } res34: Double = 150.97 scala> 20.24 + 30.5 + 100.23 res36: Double = 150.97 /// Print hash table values /// scala> dict.foldLeft(()){ case (acc, (k, v)) => println(v)} 20.24 30.5 100.23
1.8.4.5 Python
In Python 3 the function reduce is not default anymore, however it can be found in the native library functools, that has a lot of built-in functions for functional programming. The function reduce is equivalent to Haskell function foldl (fold left) which is tail recursive.
reduce(function, sequence[, initial]) -> value reduce :: (acc -> x -> acc) -> [x] ?acc0 -> acc
>>> from functools import reduce >>> >>> reduce (lambda acc, x: 10 * acc + x , [1, 2, 3, 4, 5], 0) 12345 >>> >>> f = lambda acc, x: 10 * acc + x >>> >>> f(0, 1) 1 >>> f( f(0, 1), 2) 12 >>> f( f( f(0, 1), 2), 3) 123 >>> f( f( f( f(0, 1), 2), 3), 4) 1234 >>> f( f( f( f( f(0, 1), 2), 3), 4), 5) 12345 >>> def my_reduce (f, xs, acc0=None): "Non recursive implementation of reduce (fold_left) with optional initial accumulator value. " if acc0 is None: acc = xs[0] xss = xs[1:] else: acc = acc0 xss = xs for x in xss: acc = f (acc, x) return acc >>> >>> my_reduce(lambda acc, x: 10 * acc + x, [1, 2, 3, 4, 5], 0) 12345 >>> my_reduce(lambda acc, x: 10 * acc + x, [1, 2, 3, 4, 5]) 12345 >>> my_reduce(lambda acc, x: acc + x, [1, 2, 3, 4, 5], 0) 15 >>> my_reduce(lambda acc, x: acc * x, [1, 2, 3, 4, 5], 1) 120 >>> # # Implementation without recursion. # def fold_left (f_acc_x_to_acc, acc0, xs): "Haskell-like fold left function fold_left :: (acc -> x -> acc) -> acc -> [x] " acc = acc0 for x in xs: acc = f_acc_x_to_acc (acc, x) return acc >>> fold_left (lambda acc, x: 10 * acc + x, 0, [1, 2, 3, 4, 5]) 12345 >>> def fold_right (f, acc0, xs): return fold_left ((lambda acc, x: f(x, acc)), acc0, reversed(xs)) >>> fold_right (lambda x, acc: 10 * acc + x, 0, [1, 2, 3, 4, 5]) 54321 >>> def fold_right2 (f, acc0, xs): acc = acc0 for x in reversed(xs): acc = f(x, acc) return acc >>> fold_right2 (lambda x, acc: 10 * acc + x, 0, [1, 2, 3, 4, 5]) 54321 >>>
Usefulness of Fold
Many functions and recursive algorithms can be implemented using the fold function, including map, filter, sum, product and others.
It is based in the paper:
In the paper was used fold right, here was used fold left.
def fold_left (f_acc_x_to_acc, acc0, xs): "Haskell-like fold left function fold_left :: (acc -> x -> acc) -> acc -> [x] " acc = acc0 for x in xs: acc = f_acc_x_to_acc (acc, x) return acc ;;; Function fold in curried form curry3 = lambda f: lambda x: lambda y: lambda z: f(x, y, z) fold = curry3(fold_left) >>> summation = fold(lambda acc, x: acc + x)(0) >>> >>> summation([1, 2, 3, 4, 5, 6]) 21 >>> >>> product = fold(lambda acc, x: acc * x)(1) >>> product([1, 2, 3, 4, 5]) 120 >>> >>> f_or = fold(lambda acc, x: acc or x)(False) >>> f_or([False, False, False]) False >>> >>> f_or([False, False, True]) True >>> >>> f_and = fold(lambda acc, x: acc and x)(True) >>> >>> f_and([False, True, True]) False >>> f_and([True, True, True]) True >>> >>> length = fold(lambda acc, x: acc + 1)(0) >>> length ([1, 2, 3, 4, 5]) 5 >>> _map = lambda f, xs: fold(lambda acc, x: acc + [f(x)] )([])(xs) >>> _map (lambda x: x * 3, [1, 2, 3, 4]) [3, 6, 9, 12] >>> >>> _filter = lambda p, xs: fold(lambda acc, x: (acc + [x]) if p(x) else acc )([])(xs) >>> >>> _filter(lambda x: x > 10, [10, 3, 8, 2, 20, 30]) [20, 30] >>> # # Function composition # # (f3 (f2 (f1 (f0 x)))) # # (f3 . f2 . f1 . f0) x # # or using, forward composition: # # (f0 >> f2 >> f1 >> f0) x # >>> f1 = lambda x: 3 * x >>> f2 = lambda x: 5 + x >>> f3 = lambda x: 2 ** x >>> _fcomp = lambda functions: lambda x: fold(lambda acc, f: f(acc)) (x) (functions) >>> _fcomp([f1, f2, f3])(3) 16384 >>> (f3 (f2 (f1 (3)))) 16384 >>>
1.8.4.6 Clojure
The function reduce is similar to Haskell fold left and Python reduce. This function is Polymorphic. It works on any collection of seq abstraction: lists, vectors and hash maps.
Signature:
(reduce f coll) -> reduce :: (f :: acc -> x -> acc) -> [x] Or (reduce f val coll) -> reduce :: (f :: acc -> x -> acc) -> acc -> [x] f :: acc -> x -> acc
;; Applying fold/reduce to a list ;; ;; user=> (reduce (fn [acc x] (+ (* 10 acc) x)) 0 '(1 2 3 4 5)) 12345 ;; Applying fold/reduce to a vector ;; user=> (reduce (fn [acc x] (+ (* 10 acc) x)) 0 [1 2 3 4 5]) 12345 user=> user=> (reduce (fn [acc x] (+ (* 10 acc) x)) 0 []) 0 ;; Applyind fold/reduce to a Hash map ;; user=> (reduce (fn [acc x] (cons x acc )) '() { :a 10 :b 20 :c 30 }) ([:c 30] [:b 20] [:a 10]) user=> ;; Without Initial value of accumulator it will fail on a empty list. ;; user=> (reduce (fn [acc x] (+ (* 10 acc) x)) [1 2 3 4 5]) 12345 user=> (reduce (fn [acc x] (+ (* 10 acc) x)) []) ArityException Wrong number of args (0) passed to: user/eval44/fn--45 clojure.lang.AFn.throwArity (AFn.java:429) user=> ;; Implementing fold right ;; (defn foldr ([f xs] (reduce (fn [acc x] (f x acc)) (reverse xs))) ([f acc xs] (reduce (fn [acc x] (f x acc)) acc (reverse xs))) ) user=> (foldr (fn [x acc] (+ (* 10 acc) x)) 0 [1 2 3 4 5]) 54321 ;; Clojure has destructuring ;; user=> (reduce (fn [acc [a b]] (conj acc (+ (* 10 a) b) )) '[] [[1 2] [3 4] [5 8]] ) [12 34 58] user=> ;; Implementing map with fold left (reduce) ;; user=> (defn map2 [f xs] (reverse (reduce (fn [acc x] (cons (f x) acc)) () xs))) #'user/map2 user=> user=> (map2 inc '(1 2 3 3 4 5)) (2 3 4 4 5 6) user=> ;; Implementing map with fold right ;; ;; (defn map2 [f xs] (foldr (fn [x acc] (cons (f x) acc)) () xs )) user=> (map2 inc '(1 2 3 4 5 6)) (2 3 4 5 6 7) user=>
1.8.5 For Each, Imperative map
1.8.5.1 Overview
For each is an impure higher order function which performs side-effect on each element of a list, array or sequence. Unlike map this function neither have a standard name nor returns anything.
1.8.5.2 Scheme
> (for-each (lambda (i) (display i) (newline)) '(1 2 3 4 5 6)) 1 2 3 4 5 6 > > (for-each (lambda (a b c) (display a) (display b) (display c) (newline) ) '(a b c d e f) '(1 2 3 4 5 6) '("x" "y" "z" "w" "h" "k")) a1x b2y c3z d4w e5h f6k
1.8.5.3 Haskell
> import qualified Control.Monad as M > :t M.mapM_ M.mapM_ :: Monad m => (a -> m b) -> [a] -> m () > > :t putStrLn putStrLn :: String -> IO () > > M.mapM_ putStrLn ["string 0", "string 1", "string 2", "string 3"] string 0 string 1 string 2 string 3 > > M.mapM_ (\ x -> putStrLn (show x)) [1, 2, 3, 4, 5] 1 2 3 4 5
1.8.5.4 Common Lisp
> (mapc #'print '(1 2 3 3 4)) 1 2 3 3 4
1.8.5.5 Scala
In Scala, this the higher order function is encoded as method of many Scala's data structures or collections.
// Collection List // scala> var xs = List(1.0, 2.0, 3.0, 4.0, 5.0, 6.0) xs: List[Double] = List(1.0, 2.0, 3.0, 4.0, 5.0, 6.0) scala> xs.foreach(println) 1.0 2.0 3.0 4.0 5.0 6.0 scala> xs.foreach(x => println( "x = %.3f".format(x))) x = 1,000 x = 2,000 x = 3,000 x = 4,000 x = 5,000 x = 6,000 // Collection Map, Hash map, Hashtable or dictionary. // scala> val dict = Map("x" -> 1, "y" -> 2, "z" -> 3) dict: scala.collection.immutable.Map[String,Int] = Map(x -> 1, y -> 2, z -> 3) scala> dict.foreach(println) (x,1) (y,2) (z,3) scala> dict.foreach{ case (k, v) => println(s"key = $k, value = $v") } key = x, value = 1 key = y, value = 2 key = z, value = 3 // A more practical Scala example: // scala> val files = new java.io.File("/").listFiles() files: Array[java.io.File] = Array(/lost+found, /boot, /run, ...) scala> files.foreach(println) /lost+found /boot /run /usr /etc /sbin /tmp /mnt ... ... .... ..
1.8.5.6 Ocaml
> List.iter ;; - : ('a -> unit) -> 'a list -> unit = <fun> > List.iter (fun x -> print_int x ; print_string "\n") [1 ; 2; 3; 4; 5] ;; 1 2 3 4 5 - : unit = ()
1.8.5.7 F# or FSharp
> List.iter ;; val it : (('a -> unit) -> 'a list -> unit) = <fun:clo@1> > List.iter (fun x -> printfn "x = %d" x) [1; 2; 3; 4; 5] ;; x = 1 x = 2 x = 3 x = 4 x = 5 val it : unit = () > > List.iter2 ;; val it : (('a -> 'b -> unit) -> 'a list -> 'b list -> unit) = <fun:clo@1> > - List.iter2 (fun a b -> printfn "a = %d b = %d" a b) [2; 3; 4; 5] [1; 2; 3; 4] - ;; a = 2 b = 1 a = 3 b = 2 a = 4 b = 3 a = 5 b = 4 val it : unit = () > - Array.iter ;; val it : (('a -> unit) -> 'a [] -> unit) = <fun:it@6-4> > - - Array.iter (fun x -> printfn "x = %d" x) [| 1; 2; 3; 4 |] ;; x = 1 x = 2 x = 3 x = 4 val it : unit = () >
1.8.5.8 Python
This function is not in Python standard library however, it can be defined as this.
def for_each(f, * xss): for xs in zip(* xss): f(*xs) >>> for_each (print, [1, 2, 4, 5, 6]) 1 2 4 5 6 >>> for_each (lambda a, b: print (a, b), [1, 2, 3, 4, 5, 6], ["a", "b", "c", "d", "e", "f"]) 1 a 2 b 3 c 4 d 5 e 6 f
Clojure
user=> (defn f [a b] (println (format "a = %s , b = %s" a b))) #'user/f (defn for-each [f & xss] (doseq [args (apply map vector xss)] (apply f args))) user=> (for-each println [1 2 3 4]) 1 2 3 4 nil user=> (for-each f [1 2 3 4] [3 4 5 6]) a = 1 , b = 3 a = 2 , b = 4 a = 3 , b = 5 a = 4 , b = 6 nil user=>
1.8.6 Apply
The function apply applies a function to a list or array of arguments. It is common in dynamic languages like Lisp, Scheme, Clojure, Javascript and Python.
See also: Apply Higher Oder Function - Wikipedia
Example:
Scheme
> (define (f1 x y z) (+ (* 2 x) (* 3 y) z)) > (apply f1 '(1 2 3)) $1 = 11 > (apply f1 1 2 '(3)) $2 = 11 > (apply f1 1 '(2 3)) $3 = 11 > (apply + '(1 2 3 4 5)) $1 = 15 ;;; The function apply can be used to transform a function of ;;; multiple arguments into a function of a single argument that ;;; takes a list of arguments ;;; (define (f-apply f) (lambda (xs) (apply f xs))) > (map (f-apply f1) '((1 2 3) (3 4 5) (6 7 8)) ) $2 = (11 23 41) ;; It can be also used to create a function that maps a function ;; of multiple arguments over a list of arguments. ;; (define (map-apply f xss) (map (lambda (xs) (apply f xs)) xss)) > (map-apply f1 '((1 2 3) (3 4 5) (6 7 8))) $1 = (11 23 41)
Clojure
user=> (defn f1 [x y z] (+ (* 2 x) (* 3 y) z)) #'user/f1 user=> ;; The higher order function apply is polymorphic. ;; user=> (apply f1 '(1 2 3)) 11 user=> (apply f1 [1 2 3]) 11 user=> (apply f1 1 [2 3]) 11 user=> (apply f1 1 2 [ 3]) 11 user=> (apply f1 1 2 3 [ ]) 11 user=> (apply + [1 2 3 4 5]) 15 user=> (defn map-apply [f xss] (map (fn [xs] (apply f xs)) xss)) #'user/map-apply user=> user=> (map-apply f1 [[1 2 3] [3 4 5] [6 7 8]]) (11 23 41) user=>
Python
# In Python the * asterisk notation is used to expand # a list into function arguments. # >>> f1 = lambda x, y, z: 2 * x + 3 * y + z >>> >>> f1(1, 2, 3) 11 >>> f1(*[1, 2, 3]) 11 >>> >>> def apply (f, xs): return f(*xs) ... >>> >>> apply (f1, [1, 2, 3]) 11 # # The function apply can also be defined as: # def apply2 (f, * args): return f(*(tuple(args[:-1]) + tuple(args[-1]))) >>> apply2 (f1, [1, 2, 3]) 11 >>> apply2 (f1, 1, [2, 3]) 11 >>> apply2 (f1, 1, 2, [3]) 11 >>> apply2 (f1, 1, 2, 3, []) 11 >>> >>> f_apply = lambda f: lambda xs: f(*xs) >>> >>> list(map (f_apply(f1), [[1, 2, 3], [3, 4, 5], [6, 7, 8]])) [11, 23, 41] >>> def map_apply (f, xss): return map(lambda xs: f(*xs), xss) >>> map_apply(f1, [[1, 2, 3], [3, 4, 5], [6, 7, 8]]) <map object at 0xb6daaaac> >>> >>> list(map_apply(f1, [[1, 2, 3], [3, 4, 5], [6, 7, 8]])) [11, 23, 41] >>>
1.9 Lazy Evaluation
1.9.1 Overview
"Lazy evaluation" means that data structures are computed incrementally, as they are needed (so the trees never exist in memory all at once) parts that are never needed are never computed. Haskell uses lazy evaluation by default.
Benefits
- Avoid unecessary computations
- Infinite data structure
- Separate generation from consumption
- Control-flow structures can be defined as functions
- Cyclic programming
- Ability to use Functiosn as control structures
- Define control flow (structures) as abstractions instead of primitives
Drawbacks
- Hard to predict performance
- Hard to predict space leaks
- Difficult to predict when the memory is freed
- Can lead to space leaks (aka memory leak) if not used without care (see foldl).
> let lazylist = [2..1000000000] > > let f x = x^6 > > take 5 lazylist [2,3,4,5,6] > > > {- Only the terms needed are computed. -} > take 5 ( map f lazylist ) [64,729,4096,15625,46656] >
Example in Python:
- Python uses eager evaluation by default. In order to get lazy evaluation in python the programmer must use iterators or generators. The example below uses generator.
def lazy_list(): """ Infinite list """ x = 0 while True: x += 2 yield x >>> gen = lazy_list() >>> next(gen) 2 >>> next(gen) 4 >>> next(gen) 6 >>> next(gen) 8 >>> next(gen) 10 >>> def take(n, iterable): return [next(iterable) for i in range(n)] def mapi(func, iterable): while True: yield func(next(iterable)) f = lambda x: x**5 >>> take(5, lazy_list()) [2, 4, 6, 8, 10] >>> take(10, lazy_list()) [2, 4, 6, 8, 10, 12, 14, 16, 18, 20] >>> >>> take(5, mapi(f, lazy_list())) [32, 1024, 7776, 32768, 100000] >>> >>> take(6, mapi(f, lazy_list())) [32, 1024, 7776, 32768, 100000, 248832] >>>
1.9.2 Evaluation Strategy / Parameter Passing
1.9.2.1 Call-by-value
Call-by-value (aka pass-by-value, eager evaluation, strict evaluation or applicative-order evaluation) Evaluation at the point of call, before the function application application. This evaluation strategy is used by most programming languages like Python, Scheme, Ocaml and others.
let add2xy x y = x + x + y add2xy (3 * 4) ( 2 + 3) add2xy 12 5 = 12 + 12 + 5 = 29
Example in Python:
>>> def add(x, y): ... sum = x + y ... x = sum ... return (x, sum) ... >>> >>> x = 10 >>> y = 20 # In call-by-value strategy. The function doesn't change its arguments. # >>> add(x, y) (30, 30) # They remain unchanged. # >>> x 10 >>> y 20 # Arguments are evaluated before the function invocation. # # add((10 + 20), (3 * 3)) # add(30, 9) # (39, 39) # >>> add((10 + 20),(3 * 3)) (39, 39) >>> >>> add((10 + 20),(3 / 0)) Traceback (most recent call last): File "<stdin>", line 1, in <module> ZeroDivisionError: division by zero >>>
1.9.2.2 Call-by-name
Call-by-name (aka pass-by-name): It is a non-memoized lazy evaluation. Arguments are passed non evaluated, they are only evaluated when it is needed. The arguments are substituted in the function. This evaluation strategy can be inefficient when the arguments are evaluated many times.
Example:
// Each use of x y and replaced in the function by (3 * 4) and (2 + 3) // respectively. The arguments are evaluated after substituted // in the function let add2xy x y = x + x + y let add2xy (3 * 4) (2 + 3) = (3 * 4) + (3 * 4) + (2 + 3) = 12 + 12 + 5 = 29
Call-by-name can be simulated using thunks (functions without arguments).
Example in Python:
>>> def add2xy (x, y): ... return x() + x() + y() ... >>> add2xy (lambda : (3 * 4), lambda: (2 + 3)) 29 >>>
Example in Scheme:
> (define (add2xy x y) (+ (x) (x) (y))) > ;; The parameter is evaluated every time it is used. ;; > (define (displayln msg) (display msg) (newline)) > (add2xy (lambda () (displayln "Eval x") (* 3 4)) (lambda () (displayln "Eval y") (+ 2 3)) ) Eval x Eval x Eval y 29 >
1.9.2.3 Call-by-need
Call-by-need_ (aka lazy evaluation, non-strict evaluation or normal-order evaluation): Memoized lazy-evaluation. It is a memoized version of call-by-name, after its argument is evaluated, the values are stored for further computations. When the argument evaluation has no side-effects, in other words, always yields the same output when evaluated many times it produces the same result as call-by-name. This strategy is used in Haskell.
Example: In Haskell the parameters are not evaluated at the point they are passed to the function. They are only evaluated when needed.
> let add_xy x y z = x + y > > :t add_xy add_xy :: Num a => a -> a -> t -> a > >>> div 10 2 5 >>> div 10 0 *** Exception: divide by zero >>> -- The parameter z: (3 / 0) is not evaluated -- because it is not needed. -- > add_xy 3 4 (3 / 0) 7 > >>> add_xy 3 4 (div 10 0) 7 >>> -- sum [1 ..] is not evaluated. -- If it were evaluated the computer would hang -- or trow an arithmetic overflow exception -- >>> add_xy 3 4 (sum [1 ..]) 7 >>> >>> add_xy 3 4 (div (sum [1 ..]) 0) 7 >>> -- The infinite list is not fully evaluated -- > let ones = 1:ones > take 10 ones [1,1,1,1,1,1,1,1,1,1] > > take 20 ones [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] >
1.9.2.4 Call-by-reference
- Call-by-reference (aka pass-by-reference): The function changes the value of the argument. Supported in: C++, Pascal, Python Objects.
Example in C:
// The function add10 changes it argument. // #include <stdio.h> void add10(int * x){ *x = *x + 10 ; } void main (){ int x = 5; add10(&x); printf("x = %d\n", x); }
Test:
$ gcc /tmp/test.c $ ./a.out x = 15 $ tcc -run /tmp/test.c x = 15
1.9.3 Lazy Evaluation implementation in strict languages
In strict languages with first-class function it is possible to implement lazy evaluation with "thunks" or function with no arguments wrapping an expression.
Example in F#.
// Ordinary Value //---------------------------------------- - let a = 1 + 2 + 3 + 5 + 5 ;; val a : int = 16 // Lazy Value - implementation 1 //----------------------------------------- - let b = fun () -> 1 + 2 + 3 + 4 + 5 ;; val b : unit -> int > b () ;; // Force evalution ;; val it : int = 15 > // Lazy Valye - Implementation 2 //----------------------------------- - - type Lazy<'T> = Lazy of (unit -> 'T) ;; - let force (Lazy thunk) = thunk () ; - ;; val force : Lazy<'a> -> 'a > let lazyValue = Lazy(fun () -> 1 + 2 + 3 + 5) ;; val lazyValue : Lazy<int> - force lazyValue ;; val it : int = 11 > - let lazyValue2 = Lazy(fun () -> 10 / 0 ) ;; val lazyValue2 : Lazy<int> > force lazyValue2 ;; System.DivideByZeroException: Attempted to divide by zero. at FSI_0021+lazyValue2@37.Invoke (Microsoft.FSharp.Core.Unit unitVar0) [0x00001] in <edb3af9a5a774c15bfbce9f877c6be59>:0
Lazy lists or streams like can implemented with thunks. All Haskell lists and expressions are lazy by default.
Example in F#.
/// Almost equivalent to Haskell lists type stream<'a> = | Nil | Cons of 'a * (unit -> stream<'a>) ;; > let xs0 = Nil ;; val xs0 : stream<'a> > let xs1 = Cons(10, fun () -> Nil) ;; ;; val xs1 : stream<int> > let xs2 = Cons(10, fun () -> Cons (20, fun () -> Nil)) ;; val xs2 : stream<int> let toList (xs: stream<'a>) = let rec aux acc xs = match xs with | Nil -> List.rev acc | Cons(a, thunk) -> aux (a::acc) (thunk()) aux [] xs ;; val toList : xs:stream<'a> -> 'a list - toList xs1 ;; val it : int list = [10] > - toList xs2 ;; val it : int list = [10; 20] > let take n (xs: stream<'a>) = let rec aux acc xs n = match (n, xs) with | 0, _ -> List.rev acc | _, Nil -> List.rev acc | k, Cons(a, thunk) -> aux (a::acc) (thunk()) (k - 1) aux [] xs n ;; val take : n:int -> xs:stream<'a> -> 'a list let sumSt (xs: stream<int>) = let rec aux acc xs = match xs with | Nil -> acc | Cons(a, thunk) -> aux (acc + a) (thunk()) aux 0 xs ;; val sumSt : xs:stream<int> -> int let rec mapSt fn (xs: stream<'a>): stream<'b> = match xs with | Nil -> Nil | Cons(a, thunk) -> Cons(fn a, fun () -> mapSt fn (thunk())) ;; let takeSt n (xs: stream<'a>) = let rec aux n xs = match n, xs with | 0, _ -> Nil | _, Nil -> Nil | k, Cons(a, thunk) -> Cons(a, fun () -> aux (k - 1) (thunk())) aux n xs ;; val takeSt : n:int -> xs:stream<'a> -> stream<'a> /// Create an infinite list/stream with some value // let rec repeat x = Cons (x, fun () -> repeat x) val repeat : x:'a -> stream<'a> > let ones = repeat 1 ;; val ones : stream<int> > take 3 ones ;; val it : int list = [1; 1; 1] > - take 15 ones ;; val it : int list = [1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1] > let numbers = let rec aux n = Cons(n, fun () -> aux (n + 1)) aux 0 ;; > take 2 numbers ;; val it : int list = [0; 1] > - take 12 numbers ;; val it : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11] > - takeSt 5 numbers |> toList ;; val it : int list = [0; 1; 2; 3; 4] > - takeSt 10 numbers |> toList ;; val it : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9] > > takeSt 5 numbers |> sumSt ;; val it : int = 10 > - sumSt <| takeSt 5 numbers ;; val it : int = 10 > > takeSt 10 numbers |> sumSt ;; val it : int = 45 - numbers |> mapSt (fun x -> 3 * x + 4) |> takeSt 5 |> toList ;; val it : int list = [4; 7; 10; 13; 16] > - numbers |> mapSt (fun x -> 3 * x + 4) |> takeSt 5 |> sumSt ;; val it : int = 50 > let rec unfold (fn: 'state -> ('output * 'state) option) (state: 'state) : stream<'output>= match fn state with | None -> Nil | Some (out, st) -> Cons(out, fun () -> unfold fn st) ;; val unfold : fn:('state -> ('output * 'state) option) -> state:'state -> stream<'output> let naturals = unfold (fun s -> Some (s + 1, s + 1)) 0 - takeSt 10 naturals |> toList ;; val it : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10] > let fibSerie = unfold (fun (an, an1) -> let next = an + an1 in Some (next, (an1, next))) (0, 1) > - fibSerie |> takeSt 10 |> toList ;; val it : int list = [1; 2; 3; 5; 8; 13; 21; 34; 55; 89] > - fibSerie |> takeSt 20 |> sumSt ;; val it : int = 28655 >
See also
Lazy Evaluation in OCaml and Strams (Lazy Lists)
Lazy Evaluation in SML
Matlab
Misc
- Phillip Wadler, Walid Taha and David MacQueen. How to Add laziness to a strict language without even being odd - https://www.cs.rice.edu/~taha/publications/conference/sml98.pdf
1.10 Terminology
1.10.1 Predicates
Any function that returns a boolean value, true or false. It is often used as argument to higher order functions that perform selection, decision and filtering.
Example in Scala:
// Some predicates val isEven = (x: Int) => (x % 2) == 0 val isOdd = (x: Int) => (x % 2) != 0 scala> List(1, 2, 4, 5, 6, 7, 9, 10).filter(isOdd) res1: List[Int] = List(1, 5, 7, 9) scala> List(1, 2, 4, 5, 6, 7, 9, 10).filter(isEven) res2: List[Int] = List(2, 4, 6, 10) // Example: traversing a directory. // import java.nio.file.{Files, Paths, Path} import java.util.stream.{Stream => JStream} def walkDirectory(path: String, pred: Path => Boolean)(action: Path => Unit) = Files.walk(Paths.get(path)) .filter(p => pred(p)) .forEach(p => action(p)) // Sample predicates for directory navigation // scala> val isDirectory = (p: Path) => p.toFile.isDirectory() isDirectory: java.nio.file.Path => Boolean = $$Lambda$1387/1448675410@3562b3f scala> val isFile = (p: Path) => p.toFile.isFile() isFile: java.nio.file.Path => Boolean = $$Lambda$1388/696602804@29ed425e scala> val pAll = (p: Path) => true pAll: java.nio.file.Path => Boolean = $$Lambda$1393/1337725291@705ea29 scala> def hasExtension(ext: String) = (p: Path) => p.toFile.getName.endsWith(ext) hasExtension: (ext: String)java.nio.file.Path => Boolean // Print only directories // scala> walkDirectory("/boot", isDir){ println} /boot /boot/grub /boot/grub/locale /boot/grub/themes /boot/grub/themes/starfield /boot/grub/i386-pc /boot/grub/fonts /boot/memtest86+ // Print only files // scala> walkDirectory("/boot", isFile){ println} /boot/initramfs-4.11-rt-x86_64-fallback.img /boot/intel-ucode.img /boot/linux316-x86_64.kver /boot/vmlinuz-3.16-x86_64 /boot/grub/locale/zh_CN.mo /boot/grub/locale/ru.mo /boot/grub/locale/hu.mo /boot/grub/locale/de@hebrew.mo /boot/grub/locale/nl.mo /boot/grub/locale/it.mo ... ... ... ... ... ... .. . // Print all entries // scala> walkDirectory("/boot", pAll){ println} /boot /boot/initramfs-4.11-rt-x86_64-fallback.img /boot/intel-ucode.img /boot/linux316-x86_64.kver /boot/vmlinuz-3.16-x86_64 /boot/grub /boot/grub/locale /boot/grub/locale/zh_CN.mo /boot/grub/locale/ru.mo /boot/grub/locale/hu.mo /boot/grub/locale/de@hebrew.mo /boot/grub/locale/nl.mo /boot/grub/locale/it.mo ... ... ... ... ... ... .. . // Print all files with a given extension // scala> walkDirectory("/boot", hasExtension(".img")) { file => println(s"file = $file") } file = /boot/initramfs-4.11-rt-x86_64-fallback.img file = /boot/intel-ucode.img file = /boot/grub/i386-pc/core.img file = /boot/grub/i386-pc/boot.img file = /boot/initramfs-3.16-x86_64-fallback.img file = /boot/initramfs-4.9-x86_64-fallback.img file = /boot/initramfs-3.16-x86_64.img file = /boot/initramfs-4.9-x86_64.img file = /boot/initramfs-4.11-rt-x86_64.img scala> walkDirectory("/boot", hasExtension(".png")) { file => println(s"file = $file") } file = /boot/grub/themes/starfield/boot_menu_nw.png file = /boot/grub/themes/starfield/terminal_box_n.png file = /boot/grub/themes/starfield/slider_c.png file = /boot/grub/themes/starfield/starfield.png file = /boot/grub/themes/starfield/terminal_box_nw.png file = /boot/grub/themes/starfield/boot_menu_sw.png ... ... ... ... ... ... ... ... ...
1.10.2 Thunks
A thunk is a function without any arguments that is used to delay the execution of some expression or action. Thunks allows to create higher order functions that works as control structures.
Example in Scala:
In the example below, the function doTimes has a thunk as the second argument and executes the thunk function n times.
def doTimes(n: Int, fn: () => Unit) = for(i <- 1 to n) fn() // Thunk: // // It delays the execution of the <<expression>> // () => <<expression>> // scala> val thunk1 = () => println("Functional programming is awesome!") thunk1: () => Unit = $$Lambda$1470/249666914@79d07834 scala> doTimes(5, thunk1) Functional programming is awesome! Functional programming is awesome! Functional programming is awesome! Functional programming is awesome! Functional programming is awesome scala> doTimes(5, () => println("Functional programming is awesome!")) Functional programming is awesome! Functional programming is awesome! Functional programming is awesome! Functional programming is awesome! Functional programming is awesome! def doIf[A](ifTrueFn: () => Unit, ifFalseFn: () => Unit) = (flag: Boolean) => if(flag) ifTrueFn() else ifFalseFn() scala> val action = doIf(() => println("Received true"), () => println("Received false")) action: Boolean => Unit = $$Lambda$1461/1941122645@3d400897 scala> action(true) Received true scala> action(false) Received false scala> doIf(() => println("Received true"), () => println("Received false"))(true) Received true scala> doIf(() => println("Received true"), () => println("Received false"))(false) Received false
1.10.3 Identity Function
The identity function is a polymorphic function which returns the value of its argument.
-- This is a built-in Haskell function > :t id id :: a -> a > > id 10 10 > id (Just 100) Just 100 > > let identity x = x > identity 200 200 >
1.10.4 Constant Function
The constant function returns the value of the first argument (the constant) regardless of the value of second argument.
> :t const const :: a -> b -> a > let const10 = const 10 > const10 100 10 > const10 300 10 > map const10 ["a", "b", "c", "d"] [10,10,10,10] >
Python Implementation:
>>> constant = lambda const: lambda x: const >>> >>> const10 = constant(10) >>> >>> const10(100) 10 >>> const10("hello world") 10 >>>
1.10.5 Combinators
A combinator are a set of primitive functions, operatores and higher order functions that can be combined in order to create more complex functions out of simple functions. Combinators are widespread in Haskell and one of the most famous case is Parsec the parser combinator libraries which provides parser combinator functions which allows the user build more complex parsers out of primitive parsers.
Combinators can be used to build EDSL - Embedded Domain Specific languages which are Domain Specific Language embedded in a host language or basically a library with convenient names and syntax that fits the problem domain. Parsec can be regarded as an EDSL to build parsers.
"One of the distinguishing features of functional programming is the widespread use of combinators to construct programs. A combinator is a function which builds program fragments from program fragments; in a sense the programmer using combinators constructs much of the desired program automatically, rather that writing every detail by hand."
- John Hughes - Generalizing Monads to Arrows
Example of combinators in Haskell:
- Function combinators
- id - Identity function
- const - Constant function
- (.) - Function composition
- ($) - Function application
- flip f a b = f b a
- List processing functions: map, filter, zip, fold
- Monads Combinators: Haskell's Maybe monad, Either Monad, IO Monad, …
- return, (>>=), >=> …
- Control.Monad (mapM, mapM_, forM, forM, liftM, liftM2)
- Parsec - Parser combinator library which provides higher order functions, operators and primitive functions (primitive parsers) that combined to build more complex parsers.
- Lava - Combinator library for digital circuits description and simulatioin – https://archive.alvb.in/msc/thesis/reading/lava-1999.pdf
Combinators building blocks:
- Primitive functions
- Higher order functions
- Algebraic data types
- Custom binary operators
References:
- John Hughes. Generalizing Monads to Arrows Accessed at 2017-3-0. Available at http://www.cse.chalmers.se/~rjmh/Papers/arrows.pdf
- Designing and Using Combinators: Accessed at 2017-3-0. Available at http://www.cse.chalmers.se/~rjmh/Combinators/
- Combinator pattern - HaskellWiki Accessed at 2017-3-0. Available at https://wiki.haskell.org/Combinator_pattern
- Parsec - HaskellWiki Accessed at 2017-3-0. Available at https://wiki.haskell.org/Parsec
- Combinator - HaskellWiki Accessed at 2017-3-0. Available at https://wiki.haskell.org/Combinator
- Filter combinators Accessed at 2017-3-0. Available at https://www.fh-wedel.de/~si/HXmlToolbox/thesis/x1178.html
- What is Combinators in Haskell - Stack Overflow Accessed at 2017-3-0. Available at http://stackoverflow.com/questions/20027707/what-is-combinators-in-haskell
1.11 Special Functions
1.11.1 List Constructor (Cons)
The cons operator is widely used in list recursive functions and higher order functions that operates on lists.
Scheme:
> (cons 1 (cons 2 (cons 3 (cons 4 '())))) (1 2 3 4)
Haskell:
-- Cons Operator -- > :t (:) (:) :: a -> [a] -> [a] > 1:[] [1] > 1:2:3:4:[] [1,2,3,4] > let cons = (:) > (cons 1 (cons 2 (cons 3 (cons 4 [])))) [1,2,3,4]
Ocaml and F#
> 1::[] ;; val it : int list = [1] > - 1::2::3::[] ;; val it : int list = [1; 2; 3] > - let cons x xs = x::xs ;; val cons : x:'a -> xs:'a list -> 'a list cons 1 (cons 2 (cons 3 (cons 4 []))) ;; > cons 1 (cons 2 (cons 3 (cons 4 []))) ;; val it : int list = [1; 2; 3; 4] >
1.11.2 Zip
1.11.2.1 Overview
The function zip and its variants combine two or more sequence into one sequence.
See also: Convolution (computer science)
1.11.2.2 Zip in Haskell
> :t zip zip :: [a] -> [b] -> [(a, b)] > zip [1, 2, 3, 4] ["a", "b", "c"] [(1,"a"),(2,"b"),(3,"c")] > > zip [1, 2, 3, 4] ["a", "b", "c"] [(1,"a"),(2,"b"),(3,"c")] > -- Zip a list and a infinite list > zip ["a", "b", "c"] [1 ..] [("a",1),("b",2),("c",3)] > > > zip ["a", "b", "c", "d"] [1, 2, 3] [("a",1),("b",2),("c",3)] > > :t zip3 zip3 :: [a] -> [b] -> [c] -> [(a, b, c)] > > zip3 ["a", "b", "c", "d"] [1, 2, 3, 4, 5, 6] [Just 10, Just 100, Nothing] [("a",1,Just 10),("b",2,Just 100),("c",3,Nothing)] > -- There is more zip functions in the module Data.List -- > import Data.List (zip4, zip5, zip6) > > :t zip4 zip4 :: [a] -> [b] -> [c] -> [d] -> [(a, b, c, d)] > > :t zip5 zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a, b, c, d, e)] >
1.11.2.3 Zip in Python
The Python zip function is inspired by Haskell. The Python zip functions can take a variable number of arguments.
Python 2: In python2 this function is evaluated eagerly.
>>> zip([1, 2, 3], ["a", "b", "c", "d", "e"]) [(1, 'a'), (2, 'b'), (3, 'c')] >>> >>> zip([1, 2, 3], ["a", "b", "c", "d", "e"], ["x", "y", "z"]) [(1, 'a', 'x'), (2, 'b', 'y'), (3, 'c', 'z')] >>> >>> zip([1, 2, 3], ["a", "b", "c", "d", "e"], ["x", "y", "z"], range(1, 20)) [(1, 'a', 'x', 1), (2, 'b', 'y', 2), (3, 'c', 'z', 3)] >>> >>> for x, y in zip([1, 2, 3, 4, 5], ["a", "b", "c", "d", "e"]): ... print "x = ", x, "y = ", y ... x = 1 y = a x = 2 y = b x = 3 y = c x = 4 y = d x = 5 y = e
Python 3: In python3 this function returns a generator. It is evaluated lazily.
>>> zip([1, 2, 3, 4, 5], ["a", "b", "c", "d", "e"]) <zip object at 0xb6d01ecc> >>> >>> list(zip([1, 2, 3, 4, 5], ["a", "b", "c", "d", "e"])) [(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd'), (5, 'e')] >>> >>> g = zip([1, 2, 3, 4, 5], ["a", "b", "c", "d", "e"]) >>> g <zip object at 0xb6747e8c> >>> next(g) (1, 'a') >>> next(g) (2, 'b') >>> next(g) (3, 'c') >>> next(g) (4, 'd') >>> next(g) (5, 'e') >>> next(g) Traceback (most recent call last): File "<stdin>", line 1, in <module> StopIteration >>> >>> g = zip([1, 2, 3, 4, 5], ["a", "b", "c", "d", "e"], range(1, 1000000000)) >>> g <zip object at 0xb6747f2c> >>> list(g) [(1, 'a', 1), (2, 'b', 2), (3, 'c', 3), (4, 'd', 4), (5, 'e', 5)] >>> list(g) [] >>> >>> for x, y in zip([1, 2, 3, 4, 5], ["a", "b", "c", "d", "e"]): ... print ("x = ", x, "y = ", y) ... x = 1 y = a x = 2 y = b x = 3 y = c x = 4 y = d x = 5 y = e
1.11.2.4 Zip in Scheme
It can be defined as:
(define (zip . lists) (apply map vector lists)) > (zip '(1 2 3 4) '("a" "b" "c" "d")) (#(1 "a") #(2 "b") #(3 "c") #(4 "d")) > ;; Or (define (zip . lists) (apply map list lists)) > (zip '(1 2 3 4) '("a" "b" "c" "d")) ((1 "a") (2 "b") (3 "c") (4 "d")) > > (zip '(1 2 3 4) '("a" "b" "c" "d") '(89 199 100 43)) ((1 "a" 89) (2 "b" 199) (3 "c" 100) (4 "d" 43)) >
1.11.2.5 Zip in Clojure
;; Zip returning list ;; (defn zip [& seqs] (apply map list seqs)) user=> (zip '(1 2 3 4 5) '(x y z w k m n)) ((1 x) (2 y) (3 z) (4 w) (5 k)) user=> (zip '(1 2 3 4 5) '(x y z w k m n) (range 10 1000000)) ((1 x 10) (2 y 11) (3 z 12) (4 w 13) (5 k 14)) user=> (zip '[1 2 3 4 5] '(x y z w k m n) (range 10 1000000)) ((1 x 10) (2 y 11) (3 z 12) (4 w 13) (5 k 14)) user=> (zip '[1 2 3 4 5] '(x y z w k m n) {:key_x "hello" :key_y "world" :key_z "clojure"}) ((1 x [:key_x "hello"]) (2 y [:key_y "world"]) (3 z [:key_z "clojure"])) user=> ;; Zip returning vector ;; (defn zipv [& seqs] (apply mapv vector seqs)) user=> (zipv '(1 2 3 4 5) '(x y z w k m n)) [[1 x] [2 y] [3 z] [4 w] [5 k]] user=> user=> (zipv '[1 2 3 4 5] '(x y z w k m n) (range 10 1000000)) [[1 x 10] [2 y 11] [3 z 12] [4 w 13] [5 k 14]] user=>
1.12 Function Composition
1.12.1 Overview
Function composition promotes shorter code, code reuse and higher modularity by creating new functions from previous defined ones. They also allow optimization of functional code when there is many maps. Only pure functions can be composed, function composition works like math functions, the output of one function is the input of another function. Haskell, ML, Ocaml and F# has features that makes easier to use function composition, like a lightweight syntax, currying, partially applied functions, static typing and composition operators that are built in to the language. In Haskell the operator (.) dot is used for composing functions.
See also: Function composition (computer science)
1.12.2 Function Composition in Haskell
(.) :: (b -> c) -> (a -> b) -> a -> c Given: f :: b -> c g :: a -> b (f . g ) x = f (g x) h = f . g h :: a -> c
Function Composition Block Diagram
f . g ................................ . /------\ /------\ . a --> . | g | --> | f | --> .---> c . \------/ b \------/ c . ................................ g :: a -> b f :: b -> c (.) :: (b -> c) -> (a -> b) -> a -> c
Composition Law
id . f = f Left identity law f . id = f Right identity law (f . g) . h = f . (g . h) Associativity Constant Function Composition f . const a = const (f a) const a . f = const a dentity function --> id x = x const - Constant Function --> const a b = a
Simplifying Code with function composition:
h( f ( g( x))) ==> (h . f . g ) x OR h . f . g $ x OR h $ f $ g x ==> h . f . g $ x Point Free Style composed x = h . f . g $ x ==> composed = h . f . g
Function Composition with Map
(map g (map f xs) == (map g . map f) xs = (map g . f) xs OR map g . map f == map (g . f) Generalizing map f1 (map f2 (map f3 (map f4 xs))) = (map f1) = map (f1 . f2 . f3 . f4) xs = f xs Where f = map $ f1 . f2 . f3 . f4 Example: > map (+3) [1, 2, 3, 4] [4,5,6,7] > map (*2) [4, 5, 6, 7] [8,10,12,14] > > map (*2) (map (+3) [1, 2, 3, 4]) [8,10,12,14] > > map (*2) . map (+3) $ [1, 2, 3, 4] [8,10,12,14] > > map ((*2) . (+3)) [1, 2, 3, 4] [8,10,12,14] > let f = map $ (*2) . (+3) > f [1, 2, 3, 4] [8,10,12,14]
h :: c -> [a] f :: a -> b map :: (a -> b) -> [a] -> [b] filter :: (a -> Bool) -> [a] -> [a] map f (h c) = map f . h $ c filter f (h c) = filter f . h $ c
Inverting Predicate Functions
inverted_predicate == not . predicate
> not True False > not False True > > (>5) 10 True > (>5) 3 False > not . (>5) $ 10 False > not . (>5) $ 3 True > > let f = not . (>5) > f 10 False > f 5 True > import Data.List > > filter ( isPrefixOf "a" ) ["a","ab","cd","abcd","xyz"] ["a","ab","abcd"] > > filter ( not . isPrefixOf "a" ) ["a","ab","cd","abcd","xyz"] ["cd","xyz"] >
Example:
> let f = (+4) > let g = (*3) > > > f (g 6) -- (+4) ((*3) 6) = (+4) 18 = 22 22 > > (f . g) 6 22 > > (.) f g 6 22 > > let h = f . g > > h 6 22 > > id 10 10 > id 3 3 > > id Nothing Nothing > id 'a' 'a' > id (Just 10) Just 10 > > (f . id) 10 14 > (id . f) 10 14 > > const 10 20 10 > const 10 3 10 > > (f . (const 10)) 4 14 > (f . (const 10)) 3 14 > const 10 . f $ 7 10 > const 10 . f $ 3 10 > {- Avoiding Parenthesis with composition -} > let g x = x * 2 > let f x = x + 10 > let h x = x - 5 > > h (f (g 3)) 11 > h $ f $ g 3 11 > > (h . f . g ) 3 11 > h . f . g $ 3 11 > {- Function Composition with curried functions -} > let f1 x y = 10*x + 4*y > let f2 a b c = 4*a -3*b + 2*c > let f3 x = 3*x > (f1 3 ( f3 5)) 90 > > f1 3 $ f3 5 90 > > f1 3 . f3 $ 5 90 > > let f = f1 3 . f3 > > f 5 90 > f 8 126 > > (f1 4 (f2 5 6 (f3 5))) 168 > > f1 4 $ f2 5 6 $ f3 5 168 > > f1 4 . f2 5 6 . f3 $ 5 168 > > let g = f1 4 . f2 5 6 . f3 {- You can also create new functions -} > :t g g :: Integer -> Integer > g 5 168 > g 10 288 > {- Function Composition with Map and Filter -} > import Data.Char > :t ord ord :: Char -> Int > :t ordStr ordStr :: [Char] -> [Int] > > ordStr "curry" [99,117,114,114,121] > > let r x= x + 30 > > map r (ordStr "curry") [129,147,144,144,151] > > map r $ ordStr "curry" [129,147,144,144,151] > > map r . ordStr $ "curry" [129,147,144,144,151] > > sum . map r . ordStr $ "curry" 715 > > let s = map r . ordStr > s "curry" [129,147,144,144,151] > s "haskell" [134,127,145,137,131,138,138] > let sum_ord = sum . map r . ordStr > sum_s "curry" 715 > sum_s "haskell" 950 > > sum_ord "curry" 715 > sum_ord "haskell" 950 > > map ord (map toUpper "haskell") [72,65,83,75,69,76,76] > > map ord . map toUpper $ "haskell" [72,65,83,75,69,76,76] > > map (flip (-) 10) . map ord . map toUpper $ "haskell" [62,55,73,65,59,66,66] > > map chr . map (flip (-) 10) . map ord . map toUpper $ "haskell" ">7IA;BB" > {- The function f is in point free style -} > let f = map chr . map (flip (-) 10) . map ord . map toUpper > > f "haskell" ">7IA;BB" >
1.12.3 Function Composition in Python
def compose(funclist): def _(x): y = x for f in reversed(funclist): y = f(y) return y return _ >>> add10 = lambda x: x + 10 >>> mul3 = lambda x: x * 3 >>> x = 3 >>> a = add10(x) >>> a 13 >>> b = mul3(a) >>> b 39 >>> def f_without_composition (x): ... a = add10(x) ... b = mul3(a) ... return b ... >>> f_without_composition(3) 39 >>> f_without_composition(4) 42 # It will create the function f = (mul3 ° add10)(x) # The flow is from right to left # # # (mul3 . add10) 3 # = mul3 (add10 3) # = mul3 13 # = 39 # >>> f = compose ([mul3, add10]) >>> f(3) 39 >>> f(4) 42 >>> f <function __main__.compose.<locals>._> >>> compose ([add10, mul3])(3) 39 >>> compose ([add10, mul3])(4) 42 # # Composition is more intuitive when the flow is from # left to right, the functions in the left side are # executed first. # # # Compose Forward def composef (funclist): def _(x): y = x for f in funclist: y = f(y) return y return _ # # The symbol (>>) from F# will be used to mean forward composition # here # # (add10 >> mul3) 3 # = mul3 (add10 3) # = mul3 13 # = 39 # add10 >> mul3 # Input ................................................. Output # . |----------| |---------| . 39 # 3 ---> .--> | add10 | --------> | mul3 | ------->. -------> # . 3 |----------| 13 =(10+3)|---------| 39 . # . 39 = 3 * 13 . # ................................................. # # The execution flow is from left to right, in the same order as the # functions are written in the code. # >>> g = composef ([add10, mul3]) >>> g(3) 39 >>> g(4) 42 >>> ### A more useful example: parse the following table: text = """ 12.23,30.23,892.2323 23.23,90.23,1000.23 3563.23,100.23,45.23 """ # Unfortunately Python, don't have a favorable syntax to function # composition like: composition operator, lightweight lambda and function # application without parenthesis. # >>> mapl = lambda f: lambda xs: list(map(f, xs)) >>> filterl = lambda f: lambda xs: list(filter(f, xs)) >>> splitlines = lambda s: s.splitlines() >>> reject_empty = lambda xs: list(filter(lambda x: x, xs)) >>> strip = lambda s: s.strip() >>> split = lambda sep: lambda s: s.split(sep) >>> composef([splitlines])(text) ['', ' 12.23,30.23,892.2323', ' 23.23,90.23,1000.23', ' 3563.23,100.23,45.23', ''] >>> composef([splitlines, reject_empty])(text) [' 12.23,30.23,892.2323', ' 23.23,90.23,1000.23', ' 3563.23,100.23,45.23'] >>> composef([splitlines, reject_empty, mapl(strip)])(text) ['12.23,30.23,892.2323', '23.23,90.23,1000.23', '3563.23,100.23,45.23'] >>> composef([splitlines, reject_empty, mapl(strip), mapl(split(","))])(text) [['12.23', '30.23', '892.2323'], ['23.23', '90.23', '1000.23'], ['3563.23', '100.23', '45.23']] >>> composef([splitlines, reject_empty, mapl(strip), mapl(split(",")), mapl(mapl(float))])(text) [[12.23000, 30.23000, 892.23230], [23.23000, 90.23000, 1000.23000], [3563.23000, 100.23000, 45.23000]] parse_csvtable = composef( [splitlines, reject_empty, mapl(strip), mapl(split(",")), mapl(mapl(float))] ) >>> parse_csvtable(text) [[12.23000, 30.23000, 892.23230], [23.23000, 90.23000, 1000.23000], [3563.23000, 100.23000, 45.23000]] # Notice there is three maps together, so that it can be optimized # each map is like a for loop, by composing the functions in map1, # map2 and map3 the code can be more faster. # # parse_csvtable = composef( # [splitlines, # reject_empty, # mapl(strip), ---> map1 # mapl(split(",")), ---> map2 # mapl(mapl(float))] ---> map3 # ) parse_csvtable_optmized = composef( [splitlines, reject_empty, mapl(composef([strip, split(","), mapl(float)])) ]) >>> parse_csvtable_optmized(text) [[12.23000, 30.23000, 892.23230], [23.23000, 90.23000, 1000.23000], [3563.23000, 100.23000, 45.23000]]
1.12.4 Function Composition in F#
F# uses the operator (<<) for composition which is similar to Haskell composition operator (.) dot. It also uses the operator (>>) for forward composition that performs the operation in the inverse order of operator (<<).
Composition Operator (<<):
- (<<) ;; val it : (('a -> 'b) -> ('c -> 'a) -> 'c -> 'b) > > let h x = x + 3 ;; val h : x:int -> int > let g x = x * 5 ;; val g : x:int -> int - let m x = x - 4 ;; val m : x:int -> int // The composition is performed in the same way as math composition // from right to left. // - h (g 4) ;; val it : int = 23 > - - (h << g) 4 ;; val it : int = 23 > > m (h (g 4)) ;; val it : int = 19 > - (m << h << g) 4 ;; val it : int = 19 > // It is the same as math composition: f(x) = m ° h ° g // - let f = m << h << g ;; val f : (int -> int) > f 4 ;; val it : int = 19 >
Forward Composition Operator (>>):
> (>>) ;; val it : (('a -> 'b) -> ('b -> 'c) -> 'a -> 'c) > let h x = x + 3 ;; val h : x:int -> int > let g x = x * 5 ;; val g : x:int -> int - let m x = x - 4 ;; val m : x:int -> int - h (g 4) ;; val it : int = 23 > - (g >> h) 4 ;; val it : int = 23 > - let f = g >> h ;; val f : (int -> int) > f 4 ;; val it : int = 23 > - m (h (g 4)) ;; val it : int = 19 > - - (g >> h >> m ) 4 ;; val it : int = 19 > - // The argument is seen flowing from left to right, in the inverse // order of math composition and Haskell composition operator (.) dot, // which is more easier to read. // // (g >> h >> m) 4 => It is seen as passing through each function // // Evaluating: g >> h >> m // // Input f = g >> h >> m Output // ......................................................... // . . // . |-----------| |-----------| |-----------| . // ----> |g = x * 5 ||---->| h = x + 3 |---->| m = x - 4 |-----> // 4 . |-----------| 20 |-----------| 23 |-----------| . 19 // . = 4 * 5 = 20 = 20 + 3 = 23 = 23 - 4 = 19 . // ......................................................... // - let f = g >> h >> m ;; val f : (int -> int) > f 4 ;; val it : int = 19 >
F# Argument Piping operator (|>)
- let h x = x + 3 ;; val h : x:int -> int > let g x = x * 5 ;; val g : x:int -> int > let m x = x - 4 ;; val m : x:int -> int > // The piping operator feeds the function input forward. // - (|>) ;; val it : ('a -> ('a -> 'b) -> 'b) > - (g 4) ;; val it : int = 20 > - 4 |> g ;; val it : int = 20 > // It is the same as: 4 |> g |> h // - h (g 4) ;; val it : int = 23 > - 4 |> g |> h ;; val it : int = 23 > // It is the same as: 4 |> g |> h |> m ;; // - m (h (g 4)) ;; val it : int = 19 > - 4 |> g |> h |> m ;; val it : int = 19 >
Example of a non-trivial function composition.
let text = " 12.23,30.23,892.2323 23.23,90.23,1000.23 3563.23,100.23,45.23 " ;; // Negate predicate. Invert a predicate function. // > let neg pred = fun x -> not (pred x) ;; val neg : pred:('a -> bool) -> x:'a -> bool let split_string sep str = List.ofArray (System.Text.RegularExpressions.Regex.Split (str, sep)) > let split_lines = split_string "\n" ;; val split_lines : (string -> string list) > let trim_string (s: string) = s.Trim() ;; val trim_string : s:string -> string - let is_string_empty (s: string) = s.Length = 0 - ;; val is_string_emtpy : s:string -> bool - text |> split_lines ;; val it : string list = [""; " 12.23,30.23,892.2323"; " 23.23,90.23,1000.23"; " 3563.23,100.23,45.23"; ""; ""] > - text |> split_lines |> List.filter (neg is_string_empty) ;; val it : string list = [" 12.23,30.23,892.2323"; " 23.23,90.23,1000.23"; " 3563.23,100.23,45.23"] > - text |> split_lines |> List.filter (neg is_string_empty) |> List.map trim_stri- ng ;; val it : string list = ["12.23,30.23,892.2323"; "23.23,90.23,1000.23"; "3563.23,100.23,45.23"] > - - text |> split_lines |> List.filter (neg is_string_empty) |> List.map trim_stri- ng |> List.map (split_string ",") ;; val it : string list list = [["12.23"; "30.23"; "892.2323"]; ["23.23"; "90.23"; "1000.23"]; ["3563.23"; "100.23"; "45.23"]] > - - text |> split_lines |> List.filter (neg is_string_empty) |> List.map trim_stri- ng |> List.map (split_string ",") |> List.map (List.map float) ;; val it : float list list = [[12.23; 30.23; 892.2323]; [23.23; 90.23; 1000.23]; [3563.23; 100.23; 45.23]] > // Or in multiple lines: text |> split_lines |> List.filter (neg is_string_empty) |> List.map trim_string |> List.map (split_string ",") |> List.map (List.map float) ;; val it : float list list = [[12.23; 30.23; 892.2323]; [23.23; 90.23; 1000.23]; [3563.23; 100.23; 45.23]] > // Then transformed into a function: // let parse_csv text = text |> split_lines |> List.filter (neg is_string_empty) |> List.map trim_string |> List.map (split_string ",") |> List.map (List.map float) ;; val parse_csv : text:string -> float list list > parse_csv text ;; val it : float list list = [[12.23; 30.23; 892.2323]; [23.23; 90.23; 1000.23]; [3563.23; 100.23; 45.23]] > - // This operation can be optimized with function (forward) composition. // let parse_csv2 text = text |> split_lines |> List.filter (neg is_string_empty) |> List.map (trim_string >> (split_string ",") >> (List.map float)) ;; val parse_csv2 : text:string -> float list list > parse_csv2 text ;; val it : float list list = [[12.23; 30.23; 892.2323]; [23.23; 90.23; 1000.23]; [3563.23; 100.23; 45.23]] > // It could be implemented using the math compostion (<<) operator. // in the same as in Haskell. // let parse_csv3 text = text |> split_lines |> List.filter (neg is_string_empty) |> List.map ((List.map float) << (split_string ",") << trim_string) ;; val parse_csv3 : text:string -> float list list - parse_csv3 text ;; val it : float list list = [[12.23; 30.23; 892.2323]; [23.23; 90.23; 1000.23]; [3563.23; 100.23; 45.23]] > // 934.6923 = 12.23 + 30.23 + 892.2323 // - parse_csv3 text |> List.map List.sum ;; val it : float list = [934.6923; 1113.69; 3708.69] > - - parse_csv3 text |> List.map List.sum |> List.sum ;; val it : float = 5757.0723 > // This function can also be written in point-free style. // It means only with function forward-composition. // let parse_csv4 = split_lines >> List.filter (neg is_string_empty) >> List.map (trim_string >> (split_string ",") >> (List.map float)) ;; val parse_csv4 : (string -> float list list) > parse_csv4 text ;; val it : float list list = [[12.23; 30.23; 892.2323]; [23.23; 90.23; 1000.23]; [3563.23; 100.23; 45.23]] > // With math composition (<<) or Haskell composition order. // let parse_csv5 = List.map ((List.map float) << (split_string ",") << trim_string) << List.filter (neg is_string_empty) << split_lines ;; val parse_csv5 : (string -> float list list) > parse_csv5 text ;; val it : float list list = [[12.23; 30.23; 892.2323]; [23.23; 90.23; 1000.23]; [3563.23; 100.23; 45.23]] >
1.13 Functors
1.13.1 Overview
Functors are type constructors that can be mapped over like lists are mapped with map function. This concept from category theory and like many mathematical abstractions it is defined by the laws that it must satisfies, in this case Functor's laws.
In Haskell functors are instances of the type class Functor that must implement the function fmap for each functor implementation.
Note: Haskell functors must not be confused with C++ functor and ML-module functor (Higher order module).
class Functor f where fmap :: (a -> b) -> f a -> f b
Map Diagram Functor Diagram f :: a -> b =====> f :: a -> b a ----------------------> b a ------------------------> b map f :: [a] -> [b] fmap f :: F a -> F b [a] ----------------------> [b] F a ----------------------> F b Where F is a type constructor.
A functor must satisfy the laws:
- Identity Law.
fmap id == id
Where id is the identity function.
- Composition Law
fmap (f . g) == fmap f . fmap g
The composition law can be generalized to:
fmap (f1 . f2 . f3 … fn) = fmap f1 . fmap f2 . fmap f3 … fmap fn
1.13.2 Show all Functor instances
> :info Functor class Functor f where fmap :: (a -> b) -> f a -> f b (<$) :: a -> f b -> f a -- Defined in `GHC.Base' instance Functor (Either a) -- Defined in `Data.Either' instance Functor Maybe -- Defined in `Data.Maybe' instance Functor ZipList -- Defined in `Control.Applicative' instance Monad m => Functor (WrappedMonad m) -- Defined in `Control.Applicative' instance Functor (Const m) -- Defined in `Control.Applicative' instance Functor [] -- Defined in `GHC.Base' instance Functor IO -- Defined in `GHC.Base' instance Functor ((->) r) -- Defined in `GHC.Base' instance Functor ((,) a) -- Defined in `GHC.Base' > > :info IO newtype IO a = GHC.Types.IO (GHC.Prim.State# GHC.Prim.RealWorld -> (# GHC.Prim.State# GHC.Prim.RealWorld, a #)) -- Defined in `GHC.Types' instance Monad IO -- Defined in `GHC.Base' instance Functor IO -- Defined in `GHC.Base' instance Applicative IO -- Defined in `Control.Applicative' > > :info Maybe data Maybe a = Nothing | Just a -- Defined in `Data.Maybe' instance Eq a => Eq (Maybe a) -- Defined in `Data.Maybe' instance Monad Maybe -- Defined in `Data.Maybe' instance Functor Maybe -- Defined in `Data.Maybe' instance Ord a => Ord (Maybe a) -- Defined in `Data.Maybe' instance Read a => Read (Maybe a) -- Defined in `GHC.Read' instance Show a => Show (Maybe a) -- Defined in `GHC.Show' instance MonadPlus Maybe -- Defined in `Control.Monad' instance Applicative Maybe -- Defined in `Control.Applicative' instance Alternative Maybe -- Defined in `Control.Applicative' >
1.13.3 Functor Implementations
1.13.3.1 Identity
-- File: identity.hs -- data Id a = Id a deriving (Show, Eq) instance Functor Id where fmap f (Id a) = Id (f a) -- Specialized version of fmap -- fmap_id :: (a -> b) -> (Id a -> Id b) fmap_id f = fmap f -- -- End of file identity.hs ------ ------------------------------------ > :load /tmp/identity.hs > Id 10 Id 10 > fmap (\x -> x + 3) (Id 30) Id 33 > > let plus5 = \x -> x + 5 > :t plus5 plus5 :: Integer -> Integer > > plus5 10 15 > > fmap plus5 (Id 30) Id 35 > > let fmap_plus5 = fmap plus5 <interactive>:68:18: No instance for (Functor f0) arising from a use of `fmap' The type variable `f0' is ambiguous -- Solution: > let fmap_plus5 = fmap plus5 :: Id Integer -> Id Integer > :t fmap_plus5 fmap_plus5 :: Id Integer -> Id Integer > > fmap_plus5 (Id 30) Id 35 > > :t fmap_id fmap_id :: (a -> b) -> Id a -> Id b > > fmap_id sqrt (Id 100.0) Id 10.0 > > let sqrt_id = fmap_id sqrt > :t sqrt_id sqrt_id :: Id Double -> Id Double > > sqrt_id (Id 100.0) Id 10.0 >
1.13.3.2 List
For lists the function fmap is equal to map.
instance Functor [] where fmap = map > map (\x -> x + 3) [1, 2, 3] [4,5,6] > fmap (\x -> x + 3) [1, 2, 3] [4,5,6] > > let f = fmap (\x -> x + 3) :: [Int] -> [Int] > :t f f :: [Int] -> [Int] > f [1, 2, 3, 4] [4,5,6,7] >
Alternative Implementation of list functor:
-- File: list_functor.hs -- data List a = Cons a (List a) | Nil deriving (Show, Eq) instance Functor List where fmap f xss = case xss of Nil -> Nil Cons x xs -> Cons (f x) (fmap f xs) -- End of file ------------- --------------------------- > :load /tmp/list_functor.hs > Cons 10 (Cons 20 (Cons 30 Nil)) Cons 10 (Cons 20 (Cons 30 Nil)) > > let xs = Cons 10 (Cons 20 (Cons 30 Nil)) > xs Cons 10 (Cons 20 (Cons 30 Nil)) > :t xs xs :: List Integer > > fmap (\x -> x + 5) xs Cons 15 (Cons 25 (Cons 35 Nil)) > > let fm = fmap (\x -> x + 5) :: List Integer -> List Integer > fm xs Cons 15 (Cons 25 (Cons 35 Nil)) >
1.13.3.3 Maybe / Option
data Maybe a = Just a | Nothing deriving (Eq, Show) instance Functor Maybe where fmap f (Just x) = Just (f x) fmap f Nothing = Nothing
Example:
> fmap (\x -> x + 10) (Just 5) Just 15 > > fmap (\x -> x + 10) Nothing Nothing > > let f = \x -> x + 10 > :t f f :: Integer -> Integer > > let fmap_f = fmap f :: Maybe Integer -> Maybe Integer > fmap_f (Just 20) Just 30 > > fmap_f Nothing Nothing > > import Text.Read (readMaybe) > readMaybe "100" :: Maybe Integer Just 100 > > readMaybe "asd100" :: Maybe Integer Nothing > > let parseInteger str = readMaybe str :: Maybe Integer > > :t parseInteger parseInteger :: String -> Maybe Integer > > parseInteger "100" Just 100 > > parseInteger "Not a number" Nothing > > fmap (\x -> x + 10) (parseInteger "200") Just 210 > > fmap (\x -> x + 10) (parseInteger "2sadas00") Nothing > -- Specialized version of fmap -- fmap_maybe :: (a -> b) -> (Maybe a -> Maybe b) fmap_maybe func = fmap func > fmap_maybe (\x -> x + 10) (Just 10) Just 20 > > fmap_maybe (\x -> x + 10) Nothing Nothing >
1.13.3.4 Either
The type constructor Either is similar to Maybe and it can short circuit a computation in the similar way to Maybe, however it allows to attach an error value.
data Either a b = Left a | Right b instance Functor (Either a) where fmap f (Right x) = Right (f x) fmap f (Left x) = Left x
Example:
-- -- File: either_functor.hs ------------------------- -- Specialized version of fmap to Either type -- constructor like map is specialized for lists. -- fmap_either :: (a -> b) -> (Either s a -> Either s b) fmap_either f = fmap f import Text.Read (readMaybe) data ErrorCode = ParserError | InvalidInput deriving (Eq, Show) describeErrorCode ParserError = "The parser failed." describeErrorCode InvalidInput = "Input out function domain." describeError (Right x) = Right x describeError (Left code) = Left (describeErrorCode code) parseDouble :: String -> Either String Double parseDouble str = case (readMaybe str :: Maybe Double) of Just x -> Right x Nothing -> Left "Error: Not a Double" sqrt_safe :: Double -> Either String Double sqrt_safe x = if x >= 0 then (Right x) else (Left "Error: Square root of negative number") parseDouble2 :: String -> Either ErrorCode Double parseDouble2 str = case (readMaybe str :: Maybe Double) of Just x -> Right x Nothing -> Left ParserError sqrt_safe2 :: Double -> Either ErrorCode Double sqrt_safe2 x = if x >= 0 then (Right x) else (Left InvalidInput) --------------------------------------- -- End of file - --------------------------------------- > :load /tmp/either_functor.hs > sqrt_safe 100 Right 100.0 > > sqrt_safe (-100) Left "Error: Square root of negative number" > > sqrt_safe2 100 Right 100.0 > > sqrt_safe2 (-100) Left InvalidInput > > parseDouble "100.25e3" Right 100250.0 > > parseDouble "not a double" Left "Error: Not a Double" > > parseDouble2 "-200.3" Right (-200.3) > > parseDouble2 "Not a double" Left ParserError > > fmap sqrt (Right 100.0) Right 10.0 > > fmap sqrt (Left "Error not found") Left "Error not found" > > let fmap_sqrt = fmap sqrt :: Either String Double -> Either String Double > fmap_sqrt (parseDouble "400.0") Right 20.0 > > fmap_sqrt (parseDouble "4adsfdas00.0") Left "Error: Not a Double" > > describeError (sqrt_safe2 100) Right 100.0 > > describeError (sqrt_safe2 (-100)) Left "Input out function domain." > > describeError (parseDouble2 "200.23") Right 200.23 > > describeError (parseDouble2 "2dsfsd00.23") Left "The parser failed." > > fmap_either (\x -> x + 10) (Right 200) Right 210 > > let sqrt_either = fmap_either sqrt > > :t sqrt_either sqrt_either :: Either s Double -> Either s Double > > sqrt_either (Right 100.0) Right 10.0 > > sqrt_either (Left "Failed to fetch data") Left "Failed to fetch data" >
1.13.3.5 IO
Source: Book learnyouahaskell
instance Functor IO where fmap f action = do result <- action return (f result)
-- File: fmap_io.hs -- fmap_io :: (a -> b) -> (IO a -> IO b) fmap_io f = fmap f -- ------------------ > :load /tmp/fmap_io.hs > import System.Directory (getDirectoryContents) > > :t getDirectoryContents "/etc/R" getDirectoryContents "/etc/R" :: IO [FilePath] > > getDirectoryContents "/etc/R" ["Renviron",".","ldpaths","..","repositories","Makeconf","Renviron.site","Rprofile.site"] > -- It will fail because the data is inside an IO container -- and can only be extracted inside another IO container -- or IO Monad. -- > length (getDirectoryContents "/etc/R") <interactive>:165:9: Couldn't match expected type `[a0]' with actual type `IO [FilePath]' In the return type of a call of `getDirectoryContents' In the first argument of `length', namely `(getDirectoryContents "/etc/R")' In the expression: length (getDirectoryContents "/etc/R") > fmap length (getDirectoryContents "/etc/R") 8 > :t fmap length (getDirectoryContents "/etc/R") fmap length (getDirectoryContents "/etc/R") :: IO Int > > fmap_io length (getDirectoryContents "/etc/R") 8 > > :t length length :: [a] -> Int > > let length_io = fmap_io length > > :t length_io length_io :: IO [a] -> IO Int > > fmap_io length (getDirectoryContents "/etc/R") 8 -- In the REPL is possible to extract the data wrapped inside an IO -- type constructor. -- > dirlist <- getDirectoryContents "/etc/R" > :t dirlist dirlist :: [FilePath] > > dirlist ["Renviron",".","ldpaths","..","repositories","Makeconf","Renviron.site","Rprofile.site"] > > length dirlist 8 > > :t length dirlist length dirlist :: Int >
1.14 Monads
1.14.1 Overview
A monad is a concept from Category Theory, which is defined by three things:
- a type constructor m that wraps a, parameter a;
- a return (unit) function: takes a value from a plain type and puts it into a monadic container using the constructor, creating a monadic value. The return operator must not be confused with the "return" from a function in a imperative language. This operator is also known as unit, lift, pure and point. It is a polymorphic constructor.
- a bind operator (>>=). It takes as its arguments a monadic value and a function from a plain type to a monadic value, and returns a new monadic value.
In Haskell the type class Monad specifies the type signature of all its instances. Each Monad implementation must have the type signature that matches the Monad type class.
class Monad m where -- Constructor (aka unit or lift) -- return :: a -> m a -- Bind operator -- (>>=) :: m a -> (a -> m b) -> m b (>>) :: m a -> m b -> m b fail :: String -> m a
1.14.2 Identity Monad
The identity monad is the simplest monad.
newtype Identity a = Identity { runIdentity :: a } deriving (Eq, Ord, Data, Traversable, Generic, Generic1) instance Monad Identity where return = Identity m >>= k = k (runIdentity m) instance Functor Identity where fmap = coerce instance Applicative Identity where pure = Identity (<*>) = coerce
Example:
>>> :info Identity newtype Identity a = Identity {runIdentity :: a} -- Defined in ‘Data.Functor.Identity’ instance Eq a => Eq (Identity a) -- Defined in ‘Data.Functor.Identity’ instance Monad Identity -- Defined in ‘Data.Functor.Identity’ instance Functor Identity -- Defined in ‘Data.Functor.Identity’ instance Ord a => Ord (Identity a) -- Defined in ‘Data.Functor.Identity’ instance Read a => Read (Identity a) -- Defined in ‘Data.Functor.Identity’ instance Show a => Show (Identity a) -- Defined in ‘Data.Functor.Identity’ instance MonadFix Identity -- Defined in ‘Data.Functor.Identity’ instance Applicative Identity -- Defined in ‘Data.Functor.Identity’ instance Foldable Identity -- Defined in ‘Data.Functor.Identity’ instance Traversable Identity -- Defined in ‘Data.Functor.Identity’ >>> >>> :t Identity Identity :: a -> Identity a >>> >>> Identity 10 Identity 10 >>> :t Identity 10 Identity 10 :: Num a => Identity a >>> >>> :t runIdentity runIdentity :: Identity a -> a >>> >>> runIdentity $ Identity 10 10 >>> runIdentity $ Identity 20 20 >>> >>> return 10 :: Identity Int Identity 10 >>> >>> runIdentity $ (return 10 :: Identity Int) 10 >>> return [1, 2, 3, 4] :: Identity [Int] Identity [1,2,3,4] >>> >>> fmap (\x -> x + 5) $ Identity 10 Identity 15 >>> >>> fmap (\x -> x * 4) $ fmap (\x -> x + 5) $ Identity 10 Identity 60 >>> >>> fmap ((\x -> x * 4) . (\x -> x + 5)) $ Identity 10 Identity 60 >>> >>> (return 10 :: Identity Int) >>= \x -> return $ x * 4 Identity 40 >>> >>> Identity 10 >>= \x -> return (x * 4) >>= \a -> return ( a + 5) Identity 45 >>> testidentityDO :: Identity Int -> Identity Int -> Identity Int testIdentityDO ma mb = do a <- ma b <- mb return $ a * b {- Repl friendly version -} :set +m :{ let testIdentityDO :: Identity Int -> Identity Int -> Identity Int testIdentityDO ma mb = do a <- ma b <- mb return $ a * b :} >>> testIdentityDO (Identity 10) (Identity 20) Identity 200 >>> testIdentityDO (Identity 4) (Identity 5) Identity 20 >>> {- It show how fmap can be derived from a monad. -} :{ let fmapIdentity :: (a -> b) -> Identity a -> Identity b fmapIdentity fn ma = do a <- ma return $ fn a :} >>> :t fmapIdentity fmapIdentity :: (a -> b) -> Identity a -> Identity b >>> >>> fmapIdentity (\x -> x + 5) (Identity 10) Identity 15 >>> :{ let fmapIdentity2 :: (a -> b) -> Identity a -> Identity b fmapIdentity2 fn ma = ma >>= \a -> return $ fn a :} >>> :t fmapIdentity2 fmapIdentity2 :: (a -> b) -> Identity a -> Identity b >>> >>> fmapIdentity2 (\x -> x + 5) (Identity 10) Identity 15 >>> >>> import Control.Monad (liftM2, liftM3, mapM) >>> >>> import Control.Monad (liftM2, liftM3, mapM) >>> >>> :t liftM2 liftM2 :: Monad m => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r >>> >>> liftM2 (+) (Identity 10) (Identity 30) Identity 40 >>> >>> let addIdentity = liftM2 (+) >>> addIdentity (Identity 10) (Identity 20) Identity 30 >>> >> :t liftM3 liftM3 :: Monad m => (a1 -> a2 -> a3 -> r) -> m a1 -> m a2 -> m a3 -> m r >>> >>> let cubeVolume a b c = a * b * c >>> liftM3 cubeVolume (Identity 2) (Identity 4) (Identity 5) Identity 40 >>> >>> let idCubeVolume = liftM3 cubeVolume >>> idCubeVolume (Identity 2) (Identity 4) (Identity 5) Identity 40 >>> >>> :t mapM mapM :: (Monad m, Traversable t) => (a -> m b) -> t a -> m (t b) >>> >>> mapM (\x -> Identity $ x + 4) [1, 2, 3, 4, 5] Identity [5,6,7,8,9] >>>
Documentation:
1.14.3 List Monad
1.14.3.1 List Monad in Haskell
The list Monad is used for non-deterministic computations where there is a unknown number of results. It is useful for constraint solving: solve a problem by trying all possibilities by brute force. It is equivalent to List comprehension.
In Haskell it is defined as an instance of Monad type class:
instance Monad [] where m >>= k = concat (map k m) return x = [x] fail s = []
Examples:
- return wraps a value into a list
> :t return return :: Monad m => a -> m a > -- Wraps a value into a list -- > return 10 :: [Int] [10] >
Bind operator for list monad:
> :t (>>=) (>>=) :: Monad m => m a -> (a -> m b) -> m b > > [10,20,30] >>= \x -> [2*x, x+5] [20,15,40,25,60,35] > -- It is equivalent to: -- -- > map ( \x -> [2*x, x+5] ) [10, 20, 30] [[20,15],[40,25],[60,35]] > > concat (map ( \x -> [2*x, x+5] ) [10, 20, 30]) [20,15,40,25,60,35] >
Do notation:
The do notation is a syntax sugar to -> Do Notation: Do Notation Dessugarized: cartesianProduct = do cartesianProduct = x <- [1, 2, 3, 4] [1, 2, 3, 4] >>= \x -> y <- ["a", "b"] ["a", "b"] >>= \y -> return (x, y) return (x, y) Or cartesianProduct = bind [1 2, 3, 4] (\x -> bind ["a", "b"] (\y -> unit (x, y)))
Do notation examples for List monad:
-- file cartesian.hs -- -- Run in the repl: -- :load cartesian.hs -- cartesianProduct = do x <- [1, 2, 3, 4] y <- ["a", "b"] return (x, y) -- End of file: cartesian.hs -- ----------------- > cartesianProduct [(1,"a"),(1,"b"),(2,"a"),(2,"b"),(3,"a"),(3,"b"),(4,"a"),(4,"b")] > -- Or it can be typed in the repl directly: -- > :set +m -- Enable multiline paste > -- Or copy the following code in the repl -- by typing :set +m to enable multiline paste -- :{ let cartesianProduct = do x <- [1, 2, 3, 4] y <- ["a", "b"] return (x, y) :} > :set +m -- paste > > let cartesianProduct = do *Main Control.Exception E Text.Read| x <- [1, 2, 3, 4] *Main Control.Exception E Text.Read| y <- ["a", "b"] *Main Control.Exception E Text.Read| return (x, y) *Main Control.Exception E Text.Read| > -- -- Or: Dessugarizing > [1, 2, 3, 4] >>= \x -> ["a", "b"] >>= \y -> return (x, y) [(1,"a"),(1,"b"),(2,"a"),(2,"b"),(3,"a"),(3,"b"),(4,"a"),(4,"b")] > cartesian :: [a] -> [b] -> [(a, b)] cartesian xs ys = do x <- xs y <- ys return (x, y) > cartesian [1, 2, 3, 4] ["a", "b"] [(1,"a"),(1,"b"),(2,"a"),(2,"b"),(3,"a"),(3,"b"),(4,"a"),(4,"b")] > >>> let cartesian2 xs ys = [(x, y) | x <- xs, y <- ys] >>> cartesian2 [1, 2, 3, 4] ["a", "b"] [(1,"a"),(1,"b"),(2,"a"),(2,"b"),(3,"a"),(3,"b"),(4,"a"),(4,"b")] >>> -- Returns all possible combinations between a, b and c -- -- triples :: [a] -> [b] -> [c] -> [(a, b, c)] triples xs ys zs = do x <- xs y <- ys z <- zs return (x, y, z) -- The triples have 24 results -- -- x -> 2 possibilities -- y -> 3 possibilities -- z -> 4 possibilities -- -- Total of possibilities: 2 * 3 * 4 = 24 -- the computation will return 24 results -- -- > triples [1, 2] ["a", "b", "c"] ["x", "y", "z", "w"] [(1,"a","x"),(1,"a","y"),(1,"a","z"),(1,"a","w"),(1,"b","x"), (1,"b","y"),(1,"b","z"),(1,"b","w"),(1,"c","x"),(1,"c","y"), (1,"c","z"),(1,"c","w"),(2,"a","x"),(2,"a","y"),(2,"a","z"), (2,"a","w"),(2,"b","x"),(2,"b","y"),(2,"b","z"),(2,"b","w"), (2,"c","x"),(2,"c","y"),(2,"c","z"),(2,"c","w")] > length ( triples [1, 2] ["a", "b", "c"] ["x", "y", "z", "w"] ) 24 > >>> let triples2 xs ys zs = [(x, y, z) | x <- xs, y <- ys, z <- zs] >>> :t triples2 triples2 :: [t] -> [t1] -> [t2] -> [(t, t1, t2)] >>> >>> take 3 $ triples2 [1, 2] ["a", "b", "c"] ["x", "y", "z", "w"] [(1,"a","x"),(1,"a","y"),(1,"a","z")] >>> -- -- Find all numbers for which a ^ 2 + b ^ 2 = c ^ 2 -- up to 100: -- -- There is 100 x 100 x 100 = 1,000,000 of combinations -- to be tested: -- pthytriples = do a <- [1 .. 100] b <- [1 .. 100] c <- [1 .. 100] if (a ^ 2 + b ^ 2 == c ^ 2) then (return (Just (a, b, c))) else (return Nothing) > import Data.Maybe (catMaybes) > take 10 (catMaybes pthytriples) [(3,4,5),(4,3,5),(5,12,13),(6,8,10),(7,24,25),(8,6,10),(8,15,17),(9,12,15),(9,40,41),(10,24,26)] > -- Example: Find all possible values of a functions applied -- to all combinations possible of 3 lists: -- applyComb3 = do x <- [1, 2, 3] y <- [9, 8] z <- [3, 8, 7, 4] return ([x, y, z], 100 * x + 10 * y + z) > applyComb3 [([1,9,3],193),([1,9,8],198),([1,9,7],197),([1,9,4],194) ...] -- Example: Break a 4 letter password using brute force -- -- import Data.List (find) import Data.Maybe (isJust) alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" make_password :: String -> String -> Bool make_password password input = password == input -- It will try 62 combinations for each letter -- wich means it will try up to 62 x 62 x 62 x 62 = 14,776,336 -- (=~ 15 millions) combinations at the worst case. -- -- crack_4pass pass_function = do ch0 <- alphabet ch1 <- alphabet ch2 <- alphabet ch3 <- alphabet let trial = [ch0, ch1, ch2, ch3] in if pass_function trial then return (Just trial) else return Nothing crackpass pass_function = find isJust (crack_4pass pass_function) passwd1 = make_password "fX87" > :set +s > crackpass passwd1 Just (Just "fX87") (2.00 secs, 434045068 bytes) > > crackpass (make_password "2f8z") Just (Just "2f8z") (18.19 secs, 4038359812 bytes) >
1.14.3.2 List Monad in OCaml
module ListM = struct let bind ma f = List.concat (List.map f ma) let (>>=) = bind (* return *) let unit a = [a] end ;; module ListM : sig val bind : 'a list -> ('a -> 'b list) -> 'b list val ( >>= ) : 'a list -> ('a -> 'b list) -> 'b list val unit : 'a -> 'a list end (* Haskel Code: cartesian :: [a] -> [b] -> [(a, b)] cartesian :: [a] -> [b] -> [(a, b)] cartesian xs ys = do carteasian xs ys = x <- xs ==>> xs >>= \x -> y <- ys ys >>= \y -> return (x, y) return (x, y) cartesian :: [a] -> [b] -> [(a, b)] carteasian xs ys = bind xs (\x -> bind ys (\y -> return (x, y))) *) let cartesian xs ys = let open ListM in xs >>= fun x -> ys >>= fun y -> unit (x, y) ;; val cartesian : 'a list -> 'b list -> ('a * 'b) list = <fun> > cartesian [1; 2; 3; 4; ] ["a"; "b"; "c"] ;; - : (int * string) list = [(1, "a"); (1, "b"); (1, "c"); (2, "a"); (2, "b"); (2, "c"); (3, "a"); (3, "b"); (3, "c"); (4, "a"); (4, "b"); (4, "c")] (* Haskel Code Do-natation Dessugarized triples :: [a] [b] [c] -> [(a, b, c)] triples :: [a] [b] [c] -> [(a, b, c)] triples xs ys zs = do tripes xs ys zs = x <- xs xs >>= \x -> y <- ys ==> ys >>= \y -> z <- zs zs >>= \z -> return (x, y, z) return (x, y, z) *) let triples (xs: 'a list) (ys: 'b list) (zs: 'c list) : ('a * 'b * 'c) list = let open ListM in xs >>= fun x -> ys >>= fun y -> zs >>= fun z -> unit (x, y, z) ;; val triples : 'a list -> 'b list -> 'c list -> ('a * 'b * 'c) list = <fun> > triples ["x"; "z"; "w"] [Some 10; None] [1; 2; 3; 4; 5] ;; - : (string * int option * int) list = [("x", Some 10, 1); ("x", Some 10, 2); ("x", Some 10, 3); ("x", Some 10, 4); ("x", Some 10, 5); ("x", None, 1); ("x", None, 2); ("x", None, 3); ("x", None, 4); ("x", None, 5); ("z", Some 10, 1); ("z", Some 10, 2); ("z", Some 10, 3); ("z", Some 10, 4); ("z", Some 10, 5); ("z", None, 1); ("z", None, 2); ("z", None, 3); ("z", None, 4); ("z", None, 5); ("w", Some 10, 1); ("w", Some 10, 2); ("w", Some 10, 3); ("w", Some 10, 4); ("w", Some 10, 5); ("w", None, 1); ("w", None, 2); ("w", None, 3); ("w", None, 4); ("w", None, 5)]
1.14.3.3 List Monad in F#
Example without syntax sugar:
module ListM = let bind ma f = List.concat (List.map f ma) let (>>=) = bind (* return *) let unit a = [a] ;; module ListM = begin val bind : ma:'a list -> f:('a -> 'b list) -> 'b list val ( >>= ) : ('a list -> ('a -> 'b list) -> 'b list) val unit : a:'a -> 'a list end (* Example: cartesian :: [a] -> [b] -> [(a, b)] cartesian xs ys = do x <- xs y <- ys return (x, y) > cartesian [1, 2, 3, 4] ["a", "b", "c"] *) let cartesian xs ys = let (>>=) = ListM.(>>=) in let unit = ListM.unit in xs >>= fun x -> ys >>= fun y -> unit (x, y) ;; val cartesian : 'a list -> 'b list -> ('a * 'b) list = <fun> > > > cartesian [1; 2; 3; 4; ] ["a"; "b"; "c"] ;; val it : (int * string) list = [(1, "a"); (1, "b"); (1, "c"); (2, "a"); (2, "b"); (2, "c"); (3, "a"); (3, "b"); (3, "c"); (4, "a"); (4, "b"); (4, "c")] > (* F# List type is eager evaluated so the it will really loop over 100 * 100 * 100 = 100,000,000 of combinations: pthytriples = do a <- [1 .. 100] b <- [1 .. 100] c <- [1 .. 100] if (a ^ 2 + b ^ 2 == c ^ 2) then (return (Just (a, b, c))) else (return Nothing) *) (* Tail recursive function *) let range start stop step = let rec range_aux start acc = if start >= stop then List.rev acc else range_aux (start + step) (start::acc) in range_aux start [] ;; val range : start:int -> stop:int -> step:int -> int list > range 1 11 1 ;; - : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10] let pthytriples () = let (>>=) = ListM.(>>=) in let unit = ListM.unit in range 1 101 1 >>= fun a -> range 1 101 1 >>= fun b -> range 1 101 1 >>= fun c -> if (a * a + b * b = c * c) then unit (Some (a, b, c)) else unit None ;; val pthytriples : unit -> (int * int * int) option list let option_to_list opt_list = List.foldBack (* Fold right *) (fun x acc -> match x with | Some a -> a::acc | None -> acc ) opt_list [] ;; - option_to_list (pthytriples ()) ;; val it : (int * int * int) list = [(3, 4, 5); (4, 3, 5); (5, 12, 13); (6, 8, 10); (7, 24, 25); (8, 6, 10); (8, 15, 17); (9, 12, 15); (9, 40, 41); (10, 24, 26); (11, 60, 61); (12, 5, 13); (12, 9, 15); (12, 16, 20); (12, 35, 37); (13, 84, 85); (14, 48, 50); (15, 8, 17); (15, 20, 25); (15, 36, 39); (16, 12, 20); (16, 30, 34); (16, 63, 65); (18, 24, 30); (18, 80, 82); (20, 15, 25); (20, 21, 29); (20, 48, 52); (21, 20, 29); (21, 28, 35); (21, 72, 75); (24, 7, 25); (24, 10, 26); (24, 18, 30); (24, 32, 40); (24, 45, 51); (24, 70, 74); (25, 60, 65); (27, 36, 45); (28, 21, 35); (28, 45, 53); (28, 96, 100); (30, 16, 34); (30, 40, 50); (30, 72, 78); (32, 24, 40); (32, 60, 68); (33, 44, 55); (33, 56, 65); (35, 12, 37); (35, 84, 91); (36, 15, 39); (36, 27, 45); (36, 48, 60); (36, 77, 85); (39, 52, 65); (39, 80, 89); (40, 9, 41); (40, 30, 50); (40, 42, 58); (40, 75, 85); (42, 40, 58); (42, 56, 70); (44, 33, 55); (45, 24, 51); (45, 28, 53); (45, 60, 75); (48, 14, 50); (48, 20, 52); (48, 36, 60); (48, 55, 73); (48, 64, 80); (51, 68, 85); (52, 39, 65); (54, 72, 90); (55, 48, 73); (56, 33, 65); (56, 42, 70); (57, 76, 95); (60, 11, 61); (60, 25, 65); (60, 32, 68); (60, 45, 75); (60, 63, 87); (60, 80, 100); (63, 16, 65); (63, 60, 87); (64, 48, 80); (65, 72, 97); (68, 51, 85); (70, 24, 74); (72, 21, 75); (72, 30, 78); (72, 54, 90); (72, 65, 97); (75, 40, 85); (76, 57, 95); (77, 36, 85); (80, 18, 82); (80, 39, 89); ...] >
Example with F# "workflow" or "computation expression" syntax:
- List.concat [[1]; []; [2; 3; 4; 5]; [10; 20]] ;; val it : int list = [1; 2; 3; 4; 5; 10; 20] > (* The F# workflow works like Haskell do-noation *) type ListBuilder () = member this.Bind(xs, f) = List.concat (List.map f xs) member this.Return(x) = [x] ;; type ListBuilder = class new : unit -> ListBuilder member Bind : xs:'b list * f:('b -> 'c list) -> 'c list member Return : x:'a -> 'a list end let listDo = ListBuilder () ;; val listDo : ListBuilder (* cartesian :: [a] -> [b] -> [(a, b)] cartesian xs ys = do x <- xs y <- ys return (x, y) *) let cartesian xs ys = listDo { let! x = xs let! y = ys return (x, y) } ;; val cartesian : xs:'a list -> ys:'b list -> ('a * 'b) list > cartesian [1; 2; 3; 4; ] ["a"; "b"; "c"] ;; val it : (int * string) list = [(1, "a"); (1, "b"); (1, "c"); (2, "a"); (2, "b"); (2, "c"); (3, "a"); (3, "b"); (3, "c"); (4, "a"); (4, "b"); (4, "c")] >
1.14.3.4 List Monad in Python
from functools import reduce def concat(xss): "concat :: [[a]] -> [a]" return reduce(lambda acc, x: acc + x, xss, []) def listUnit (x): "listUnit :: x -> [x]" return [x] def listBind (xss, f): "listBind :: [a] -> (a -> [b]) -> [b] " return concat(map(f, xss)) # Haskel Code: # # cartesian :: [a] -> [b] -> [(a, b)] cartesian :: [a] -> [b] -> [(a, b)] # cartesian xs ys = do carteasian xs ys = # x <- xs ==>> xs >>= \x -> # y <- ys ys >>= \y -> # return (x, y) return (x, y) # # # cartesian :: [a] -> [b] -> [(a, b)] # carteasian xs ys = # bind xs (\x -> # bind ys (\y -> # return (x, y))) # def cartesian(xs, ys): return listBind(xs, lambda x: listBind(ys, lambda y: listUnit ((x, y)))) def triples(xs, ys, zs): return listBind(xs, lambda x: listBind(ys, lambda y: listBind(zs, lambda z: listUnit((x, y, z))))) >>> cartesian([1, 2, 3, 4], ["a", "b", "c"]) [(1, 'a'), (1, 'b'), (1, 'c'), (2, 'a'), (2, 'b'), (2, 'c'), (3, 'a'), (3, 'b'), (3, 'c'), (4, 'a'), (4, 'b'), (4, 'c')] >>> >>> triples([1, 2], ["a", "b", "c"], ["x", "y", "z"]) [(1, 'a', 'x'), (1, 'a', 'y'), (1, 'a', 'z'), (1, 'b', 'x'), (1, 'b', 'y'), (1, 'b', 'z'), (1, 'c', 'x'), ... >>> # Emulate ML module # class ListM (): @classmethod def bind(cls, xss, f): return concat(map(f, xss)) @classmethod def unit(cls, x): return [x] def cartesian (xs, ys): return ListM.bind( xs, lambda x: ListM.bind( ys, lambda y: ListM.unit ((x, y)))) >>> cartesian([1, 2, 3, 4], ["a", "b", "c"]) [(1, 'a'), (1, 'b'), (1, 'c'), (2, 'a'), (2, 'b'), (2, 'c'), (3, 'a'), (3, 'b'), (3, 'c'), (4, 'a'), (4, 'b'), (4, 'c')] >>>
1.14.4 Maybe / Option Monad
1.14.4.1 Overview
The Maybe type (Haskell) or Option type (ML, F# and OCaml) is used to indicate that a function might return nothing, the value might not exists or that a computation maight fail. This is helpful to remove nested null checks, avoid null pointer or null object exceptions.
Some functions are a natural candidates to return a maybe or option type like parser function, user input validation, lookup functions that search an input in data structure or database and functions with invalid input.
1.14.4.2 Maybe Monad in Haskell
The Maybe monad ends the computation if any step fails. The module Data.Maybe has useful function to deal with Maybe type.
data Maybe a = Just a | Nothing instance Monad Maybe where (Just x) >>= k = k x Nothing >>= k = Nothing return = Just
Example: The function below parses two numbers and adds them.
--- File: test.hs -- import Data.List (lookup) import Text.Read (readMaybe) -- Parser functions parseInt :: String -> Maybe Int parseInt x = readMaybe x :: Maybe Int parseDouble :: String -> Maybe Double parseDouble x = readMaybe x :: Maybe Double -- Function with invalid input sqrtSafe :: Double -> Maybe Double sqrtSafe x = if x > 0 then Just (sqrt x) else Nothing addSafe :: Maybe Double -> Maybe Double -> Maybe Double addSafe some_x some_y = do x <- some_x y <- some_y return (x + y) addOneSafe :: Maybe Double -> Double -> Maybe Double addOneSafe a b = do sa <- a let c = 3.0 * (b + sa) return (sa + c) -- s - stands for Some -- addSqrtSafe :: Double -> Double -> Maybe Double addSqrtSafe x y = do sx <- sqrtSafe x sy <- sqrtSafe y return (sx + sy) -- addSqrtSafe desugarized -- addSqrtSafe2 x y = sqrtSafe x >>= \sx -> sqrtSafe y >>= \sy -> return (sx + sy) -- End of test file -------------------------------- > :load /tmp/test.hs > :t readMaybe readMaybe :: Read a => String -> Maybe a > > parseInt "100" Just 100 -- Returns nothing if computation fails -- instead of perform an exception -- > parseInt "not an int." Nothing > > parseDouble "1200" Just 1200.0 > parseDouble "1200.232" Just 1200.232 > parseDouble "12e3" Just 12000.0 > parseDouble "not a valid number" Nothing > -- This haskell function is safe, however in another language -- it would yield a exception. -- > sqrt (-100.0) NaN > > sqrtSafe (-1000.0) Nothing > > sqrtSafe 100.0 Just 10.0 > -- Thea function fmap is a generalization of map and applies a function -- to the value wrapped in the monad. -- > :t fmap fmap :: Functor f => (a -> b) -> f a -> f b > > fmap (\x -> x + 1.0) (Just 10.0) Just 11.0 > fmap (\x -> x + 1.0) Nothing Nothing > > fmap (\x -> x + 1.0) (parseDouble "10.233") Just 11.233 > fmap (\x -> x + 1.0) (parseDouble "ase10.2x3") Nothing > -- return function -- > :t return return :: Monad m => a -> m a > return 10 :: Maybe Int Just 10 > > return "hello world" :: Maybe String Just "hello world" > -- Bind function -- -- The bind operator or funciton short circuits the computation if -- it fails at any point -- -- > :t (>>=) (>>=) :: Monad m => m a -> (a -> m b) -> m b > > Just "100.0" >>= parseDouble >>= sqrtSafe Just 10.0 > > Nothing >>= parseDouble >>= sqrtSafe Nothing > > return "100.0" >>= parseDouble >>= sqrtSafe Just 10.0 > > return "-100.0" >>= parseDouble >>= sqrtSafe Nothing > -- Do noation -- -- -- addSafe some_x some_y = do addSafe = do -- x <- some_x some_x >>= \x -> -- y <- some_y ==> some_y >>= \y -> -- return (x + y) return (x + y) -- -- -- -- -- > :t addSafe addSafe :: Maybe Double -> Maybe Double -> Maybe Double > > addSafe (Just 100.0) (Just 20.0) Just 120.0 > > addSafe (Just 100.0) Nothing Nothing > > addSafe Nothing (Just 100.0) Nothing > > addSafe Nothing Nothing Nothing > > addSafe (parseDouble "100.0") (sqrtSafe 400.0) Just 120.0 > > addSafe (Just 100.0) (sqrtSafe (-20.0)) Nothing > > addSafe (parseDouble "asd100.0") (sqrtSafe 400.0) Nothing > > :t addSqrtSafe addSqrtSafe :: Double -> Double -> Maybe Double > > addSqrtSafe 100.0 400.0 Just 30.0 > > addSqrtSafe (-100.0) 400.0 Nothing > > addSqrtSafe2 (-100.0) 400.0 Nothing > addSqrtSafe2 100.0 400.0 Just 30.0 > > addOneSafe (Just 10.0) 20.0 Just 100.0 > > addOneSafe Nothing 20.0 Nothing > > addOneSafe (parseDouble "100.0") 20.0 Just 460.0 > > addOneSafe (parseDouble "1dfd00.0") 20.0 Nothing >
1.14.4.3 Maybe Monad in OCaml
The maybe type is called Option in Ocaml and F#.
-> Some 100 ;; - : int option = Some 100 -> None ;; - : 'a option = None module OptM = struct let unit x = Some x let bind ma f = match ma with | Some x -> f x | None -> None let (>>=) = bind (* Haskell fmap *) let map f ma = match ma with | Some x -> Some (f x) | None -> None end module OptM : sig val unit : 'a -> 'a option val bind : 'a option -> ('a -> 'b option) -> 'b option val ( >>= ) : 'a option -> ('a -> 'b option) -> 'b option val map : ('a -> 'b) -> 'a option -> 'b option end # OptM.unit ;; - : 'a -> 'a option = <fun> # OptM.bind ;; - : 'a option -> ('a -> 'b option) -> 'b option = <fun> # # OptM.map ;; - : ('a -> 'b) -> 'a option -> 'b option = <fun> # # OptM.map (fun x -> x + 3) (Some 10) ;; - : int option = Some 13 # OptM.map (fun x -> x + 3) None ;; - : int option = None # float_of_string "100.23" ;; - : float = 100.23 # float_of_string "a100.23" ;; Exception: Failure "float_of_string". let parseFloat x = try Some (float_of_string x) with _ -> None ;; # parseFloat "100.00" ;; - : float option = Some 100. # # parseFloat "asds100.00" ;; - : float option = None # (* addSafe :: Maybe Double -> Maybe Double -> Maybe Double addSafe some_x some_y = do x <- some_x y <- some_y return (x + y) addSafe some_x some_y = some_x >>= \x -> some_y >>= \y -> return (x + y) *) let addSafe sx sy = let open OptM in sx >>= fun x -> sy >>= fun y -> unit (x +. y) ;; val addSafe : float option -> float option -> float option = <fun> # addSafe (Some 10.0) (Some 20.0) ;; - : float option = Some 30. # addSafe None (Some 20.0) ;; - : float option = None # addSafe None None ;; - : float option = None # (* If Haskell functions were impure it would work: addInputsSafe () = do x <- parseDouble (readLine ()) y <- parseDouble (readLine ()) z <- parseDouble (readLine ()) return (x + y + z) addInputsSafe some_x some_y = readLine () >>= \x -> readLine () >>= \y -> readLine () >>= \x -> return (x + y + z) *) let prompt message = print_string message ; parseFloat (read_line()) ;; val prompt : string -> float option = <fun> let addInputsSafe () = let open OptM in prompt "Enter x: " >>= fun x -> prompt "Enter y: " >>= fun y -> prompt "Enter z: " >>= fun z -> unit (print_float (x +. y +. z)) ;; val addInputsSafe : unit -> unit option = <fun> (* It will stop the computation if any input is invalid *) # addInputsSafe () ;; Enter x: 10.0 Enter y: 20.0 Enter z: 30.0 60.- : unit option = Some () # # addInputsSafe () ;; Enter x: 20.0 Enter y: dsfd - : unit option = None # - : addInputsSafe () ;; Enter x: 20.0 Enter y: 30.0 Enter z: a20afdf - : unit option = None # addInputsSafe () ;; Enter x: erew34 - : unit option = None #
1.14.4.4 Maybe Monad in Python
Implementation with Functions
import collections Option = collections.namedtuple("Option", ["value"]) # Nothing none = Option(None) # Just some = Option # Haskell's return statement # unit_option = some def isOption(obj): return isinstance(obj, Option) def isOptionException(obj): if isinstance (obj, Option): return obj else: raise ValueError ("Expected an instance of Option") # isJust def isSome (opt): return not (isOptionException(opt).value == None) # isNothing def isNone (opt): return not(isSome (opt)) def fmap_option(fn, opt): if isSome(opt): return some(fn(opt.value)) else: return none def bind_option(opt, fn): if isSome(opt): return fn(opt.value) else: return none def parseFloat (x): "parseFloat :: string -> Option float" try: return some(float(x)) except ValueError: return none def addSafe(opt_x, opt_y): " addSafe :: option float -> option float -> option float The same as Haskell addSafe Maybe Double -> Maybe Double -> Maybe Double addSafe opt_x opt_y = do x <- opt_x y <- opt_y return (x + y) addSafe opt_x opt_y = opt_x >>= \x -> opt_y >>= \y -> return (x + y) " return bind_option(opt_x, lambda x: bind_option(opt_y, lambda y: unit_option (x + y))) def prompt(message): "prompt :: string -> Option float" print (message) return parseFloat(input ()) def addInputsSafe (): return bind_option(prompt("Enter x:"), lambda x: bind_option(prompt("Enter y:"), lambda y: bind_option(prompt("Enter z:"), lambda z: unit_option (x + y + z)))) >>> some(100) Option(value=100) >>> none Option(value=None) >>> >>> fmap_option(lambda x: x * 5, some(10)) Option(value=50) >>> >>> fmap_option(lambda x: x * 5, none) Option(value=None) >>> >>> addSafe(some(100), none) Option(value=None) >>> addSafe(some(100), some(200)) Option(value=300) >>> addSafe(none, none) Option(value=None) >>> >>> float("10asdas023") Traceback (most recent call last): File "<stdin>", line 1, in <module> ValueError: could not convert string to float: '10asdas023' >>> >>> parseFloat("100.0") Option(value=100.0) >>> parseFloat("10asda0.0") Option(value=None) >>> >>> addSafe(parseFloat("100"), parseFloat("200")) Option(value=300.0) >>> >>> addSafe(parseFloat("100"), parseFloat("2dsfsd00")) Option(value=None) >>> >>> >>> addSafe(parseFloat("asdas"), parseFloat("2dsfsd00")) Option(value=None) >>> # # Computation is stopped if any step go wrong # >>> >>> addInputsSafe () Enter x: 100 Enter y: 200 Enter z: 300 Option(value=600.0) >>> >>> addInputsSafe () Enter x: asdsa Option(value=None) >>> >>> addInputsSafe () Enter x: 100 Enter y: sadas Option(value=None) >>>
Implementation with Class
class Option(): def __init__(self, value): self.value = value def __str__(self): if self.isSome(): return "some {}".format(self.value) else: return "none" def __repr__(self): return self.__str__() def isSome (self): return (self.value != None) def isNone (self): return (self.value == None) # fmap def map(self, fn): if self.isSome(): return Option(fn(self.value)) else: return Option(None) def bind(self, fn): if self.isSome(): return fn(self.value) else: return Option(None) some = Option none = Option(None) def parseFloat (x): "parseFloat :: string -> Option float" try: return some(float(x)) except ValueError: return none >>> parseFloat("100.23") Option(value=100.23) >>> parseFloat("100asdas.23") Option(value=None) >>> >>> parseFloat("10.5").map(lambda x: x * 3) some 31.5 >>> parseFloat("1sdfsd0.5").map(lambda x: x * 3) none >>> >>> (parseFloat("10.5") .map(lambda x: x * 3) .map(lambda x: x + 4) .map(lambda x: x * x) ) >>> ... ... ... ... some 1260.25 >>> >>> (parseFloat("10asdas.5") .map(lambda x: x * 3) .map(lambda x: x + 4) .map(lambda x: x * x) ) >>> ... ... ... ... none >>> >>> some("10.5").bind(parseFloat) some 10.5 >>> >>> some("1sdf0.5").bind(parseFloat) none >>> >>> some("10.5").bind(parseFloat).map(lambda x: x + 10) some 20.5 >>> some("10sdf.5").bind(parseFloat).map(lambda x: x + 10) none >>> # Haskell's code # def addSafe(opt_x, opt_y): # addSafe opt_x opt_y = addSafe opt_x opt_y = return opt_x.bind(lambda x: # opt_x >>= \x -> bind opt_x (\x -> opt_y.bind(lambda y: # opt_y >>= \y -> ==> bind opt_y (\y -> Option(x + y))) # return (x + y) return (x + y))) >>> >>> addSafe(some(10), some(20)) some 30 >>> addSafe(some(10), none) none >>> addSafe(none, none) none >>> addSafe(none, some(30)) none >>> addSafe(parseFloat("10"), parseFloat("15")) some 25.0 >>> >>> addSafe(parseFloat("10"), parseFloat("1asd5")) none >>> addSafe(parseFloat("1asd0"), parseFloat("1asd5")) none >>>
1.14.5 Either Monad
1.14.5.1 Overview
The Either type is an extension of Maybe, it end a computation if any step fails. Unlike Maybe it can indicate the source of the error. It represents two values Right that holds a correct value (mneumonic "right" meaning correct) and the constructor Left that holds an error value.
The module Data.Either has combinators to manipulate the Either type.
From: src/Control/Monad/Either.hs
data Either a b = Left a | Right b deriving (Eq, Show) instance Monad (Either e) where return = Right Right m >>= k = k m Left e >>= _ = Left e
1.14.5.2 Example
file: either_monad.hs
-- File: either_monad.hs ------------------------------ import Text.Read (readMaybe) data ErrorCode = ParserError | InvalidInput deriving (Eq, Show) describeErrorCode ParserError = "The parser failed." describeErrorCode InvalidInput = "Input out function domain." describeError (Right x) = Right x describeError (Left code) = Left (describeErrorCode code) parseDouble2 :: String -> Either ErrorCode Double parseDouble2 str = case (readMaybe str :: Maybe Double) of Just x -> Right x Nothing -> Left ParserError sqrt_safe2 :: Double -> Either ErrorCode Double sqrt_safe2 x = if x >= 0 then (Right x) else (Left InvalidInput) addSafe1 :: Either err Double -> Either err Double -> Either err Double addSafe1 ex ey = do x <- ex y <- ey return $ x + y addSafe2 :: Either err Double -> Either err Double -> Either err Double addSafe2 ex ey = ex >>= \x -> ey >>= \y -> return (x + y) test1 input = do x <- parseDouble2 input y <- sqrt_safe2 x return (x + y) test2 input = parseDouble2 input >>= \x -> sqrt_safe2 x >>= \y -> return (x + y) -- ----- End of File -------------------- ------------------------------------------
Repl:
> :load /tmp/either_monad.hs -- Playing with Return -- > return 10 :: Either a Double Right 10.0 > > let returnEither x = Right x > > returnEither 10 Right 10 > returnEither 10.0 Right 10.0 > :t returnEither 10.0 returnEither 10.0 :: Fractional b => Either a b > > :t returnEither (10.0 :: Double) returnEither (10.0 :: Double) :: Either a Double > --- Playing with bind operator --- > Right 10 >>= \x -> Right (x + 5) Right 15 > > return 10 >>= \x -> Right (x + 5) Right 15 > > Right 10 >>= \x -> Left "It always will fail" Left "It always will fail" > > Left "Computation failed" >>= \x -> Right (x + 5) Left "Computation failed" > > return 5 >>= \x -> if x < 20 then Right (x + 5) else Left "Number out of range greater than 20" Right 10 > > return 30 >>= \x -> if x < 20 then Right (x + 5) else Left "Number out of range greater than 20" Left "Number out of range greater than 20" > > return "100.23" >>= \x -> parseDouble2 x Right 100.23 > > return "1dsf00.23" >>= \x -> parseDouble2 x Left ParserError > > test1 "100.0" Right 200.0 > > > test1 "asd100.0" Left ParserError > > > test1 "-100" Left InvalidInput > > test2 "100" Right 200.0 > > test2 "asdd10sd0" Left ParserError > > test2 "-200" Left InvalidInput > > :t addSafe1 addSafe1 :: Either err Double -> Either err Double -> Either err Double > > addSafe1 (Right 100) (Right 200) Right 300.0 > > addSafe1 (Right 100) (Left "Error: second argument not a number") Left "Error: second argument not a number" > > addSafe1 (Left "Error: first argument not a number") (Right 100) Left "Error: first argument not a number" > > addSafe1 (parseDouble2 "200.0") (sqrt_safe2 100.0) Right 300.0 > > addSafe1 (parseDouble2 "200.0") (sqrt_safe2 (-100.0)) Left InvalidInput > > addSafe1 (parseDouble2 "2sdfs00.0") (sqrt_safe2 (-100.0)) Left ParserError > > addSafe2 (parseDouble2 "200.0") (sqrt_safe2 100.0) Right 300.0 > > describeError $ addSafe2 (parseDouble2 "20asdas0.0") (sqrt_safe2 100.0) Left "The parser failed." > > describeError $ addSafe2 (parseDouble2 "2000.0") (sqrt_safe2 (-100.0)) Left "Input out function domain." > > import qualified Data.Either as E -- Extracts from a list of Either all the Left elements All the Left -- elements are extracted in order. -- > E.lefts [Left "Error 1", Right 10, Left "Error 2", Right 200] ["Error 1","Error 2"] > -- Extracts from a list of Either all the Right elements All the Right -- elements are extracted in order. -- > E.rights [Left "Error 1", Right 10, Left "Error 2", Right 200] [10,200] > > E.partitionEithers [Left "Error 1", Right 10, Left "Error 2", Right 200] (["Error 1","Error 2"],[10,200]) > -- Case analysis for the Either type. If the value is Left a, apply -- the first function to a; if it is Right b, apply the second -- function to b. -- > :t E.either E.either :: (a -> c) -> (b -> c) -> Either a b -> c > > E.either (\left -> left + 10) (\right -> right * 3) (Right 10) 30 > > E.either (\left -> left + 10) (\right -> right * 3) (Left 10) 20 > > let f = E.either (\left -> left + 10) (\right -> right * 3) > :t f f :: Either Integer Integer -> Integer > > f (Right 10) 30 > f (Left 10) 20 >
1.14.6 IO Monad
1.14.6.1 IO Actions
The type IO indicates an action that when evaluated may perform some
IO. The function putChar :: Char -> IO ()
takes a char and returns
an IO action that prints a char, no character is printed on the
screen and no side-effect is performed. This IO action can be passed
as a ordinary values to other IO actions and combined with other IO
actions. IO actions only will be executed when called from the main IO
action main :: IO ()
or called from other IO actions called from
main.
The values wrapped in an IO type like getChar :: IO Char
can only be
extracted inside an IO action.
Summary:
- The Haskell's IO is pure and lazy.
- The IO action type separates the definition from execution.
- All functions that returns IO actions are pure functions.
- There is no way to extract a value of an IO action outside an IO action.
- Only IO actions perform IO actions.
- The entry point of a Haskell program is the main IO action. Only the IO action executed from main will be executed.
- IO actions are not functions. IO actions are values that can be passed to functions and stored in data structures like any other value.
- IO Actions are commands.
_putSTrln "str"_
doesn't print a string. It actually creates a command to print a string that can be manipulated like a value, repeated, stored in data structures and passed to another IO actions. - By typing the name of an IO action in the REPL (ghci) the user forces its execution.
Reading type signatures:
- main is an IO action, not a function.
main :: IO main = do putStrLn "hello"
- putStrLn is a function which takes a string and returns an IO action which produces nothing '()' unit value.
putStrLn :: String -> IO ()
- printMsg is a IO action, that when executed, will print a string.
printMsg :: IO () printMSg = putStrLn "Hello world"
- getLine is an IO action that when executed produces a string. It is not a function.
getLine :: IO String
- readFile is a function that takes a string and returns an IO action which when executed produces a string.
readFile :: FilePath -> IO String
Example: IO actions are execute only when forced to do so.
It is noticeable that:
- action2 neither action3 are executed and they don't print anything.
- Only the IO actions called from main are executed.
- The string returned by the IO action askQuestion can only be extracted inside an IO action.
file: haskell_io1.hs
import System.IO (hFlush, stdout) action1 :: IO () action1 = putStrLn "Say action 1 dummy" -- action2 :: IO () action2 = putStrLn "Action2 won't be executed" action3 :: IO () action3 = putStrLn "Action3 won't be executed" newline :: IO () newline = putStrLn "" -- prompt :: String -> IO String prompt message = do putStr message hFlush stdout line <- getLine newline newline return line askQuestion :: IO String askQuestion = prompt "> Enter a line: " main :: IO () main = do putStrLn "Hello world" action1 line <- askQuestion putStrLn ("You entered the line: " ++ line)
Compiling and running:
# Compiling $ ghc haskell_test.hs [1 of 1] Compiling Main ( haskell_test.hs, haskell_test.o ) Linking haskell_test ... # Running the executable # $ ./haskell_test Hello world Say action 1 dummy > Enter a line: Hola mundo. Muchas gracias Haskell! You entered the line: Hola mundo. Muchas gracias Haskell! # Executing in batch mode (script) # $ runghc haskell_test.hs Hello world Say action 1 dummy > Enter a line: Hola mundo Haskell. You entered the line: Hola mundo Haskell.
Example: IO Actions can be stored in data structures and passed as values
:{ printFile :: String -> IO () printFile file = do content <- readFile file putStrLn content :} let printHello = putStrLn "Hello" let printWorld = putStrLn "world" let actionList = [printHello, printWorld, printFile "/etc/issue", print [1..10]] Prelude> :t actionList actionList :: [IO ()] Prelude> :{ runActions :: [IO()] -> IO () runActions ioList = do case ioList of [] -> return () (ioAction:rest) -> do ioAction runActions rest :} Prelude> runActions actionList Hello world Manjaro Linux \r (\n) (\l) [1,2,3,4,5,6,7,8,9,10] Prelude> Prelude> let actions = [putStrLn "hello world (en)", putStrLn "hola mundo (es)", putStrLn "ola mundo (pt)"] Prelude> Prelude> :t actions actions :: [IO ()] Prelude> Prelude> runActions actions hello world (en) hola mundo (es) ola mundo (pt) Prelude> {- | Note that Haskell has a function for this: sequence_ -} > import Control.Monad (sequence_) > :t sequence_ sequence_ :: (Foldable t, Monad m) => t (m a) -> m () > sequence_ actionList Hello world Manjaro Linux \r (\n) (\l) [1,2,3,4,5,6,7,8,9,10] > > sequence_ actions hello world (en) hola mundo (es) ola mundo (pt) > -- IO actions can be passed as values and manipulated as values -- :{ doTimes :: Int -> IO () -> IO () doTimes n action = do if n < 0 then error "Error: n cannot be negative" else case n of 0 -> return () k -> do action doTimes (k - 1) action :} Prelude> :t doTimes doTimes :: Int -> IO () -> IO () Prelude> Prelude> doTimes 3 (putStrLn "hello world") hello world hello world hello world Prelude> Prelude> doTimes 8 (putStrLn "hello world") hello world hello world hello world hello world hello world hello world hello world hello world Prelude> > doTimes 3 (sequence_ actionList) Hello world Manjaro Linux \r (\n) (\l) [1,2,3,4,5,6,7,8,9,10] Hello world Manjaro Linux \r (\n) (\l) [1,2,3,4,5,6,7,8,9,10] Hello world Manjaro Linux \r (\n) (\l) [1,2,3,4,5,6,7,8,9,10] >
IO Actions allow to write functions that works like control structures.
:{ myIF :: Bool -> IO () -> IO () -> IO () myIF cond actionThen actionElse = if cond then actionThen else actionElse :} > myIF True (putStrLn "Turn on control valve") (putStrLn "Shutdown control valve") Turn on control valve > > myIF False (putStrLn "Turn on control valve") (putStrLn "Shutdown control valve") Shutdown control valve > > :{ myWhen :: Bool -> IO () -> IO () myWhen cond action = if cond then action else return () :} > myWhen True (putStrLn "Fire missiles") Fire missiles > myWhen False (putStrLn "Fire missiles") > > import Text.Read (readMaybe) > {- | Read input from user until he provides a valid value. -} :{ readUntil :: Read a => String -> IO a readUntil prompt = do putStr prompt input <- getLine case readMaybe input of Nothing -> do putStrLn "Error: Enter a valid value." readUntil prompt Just x -> return x :} > :t readUntil readUntil :: Read a => IO a > > readUntil "> Enter a number: " :: IO Int > Enter a number: dsfsd Error: Enter a valid value. > Enter a number: 234dsfsd Error: Enter a valid value. > Enter a number: 145 145 > > readUntil "> Enter a Maybe number: " :: IO (Maybe Int) > Enter a Maybe number: dsfsd Error: Enter a valid value. > Enter a Maybe number: 345sa Error: Enter a valid value. > Enter a Maybe number: 2343 Error: Enter a valid value. > Enter a Maybe number: Just 100 Just 100 > {- | IO Actions can be composed -} :{ sumTwoNumbers :: IO () sumTwoNumbers = do number1 <- readUntil "Enter number 1: " :: IO Int number2 <- readUntil "Enter number 2: " :: IO Int let s = number1 + number2 putStrLn ("The sum is equal to " ++ show s) :} > sumTwoNumbers Enter number 1: sada Error: Enter a valid value. Enter number 1: 3423asd Error: Enter a valid value. Enter number 1: Error: Enter a valid value. Enter number 1: 1000^?^? Error: Enter a valid value. Enter number 1: 2- Error: Enter a valid value. Enter number 1: 200 Enter number 2: dsafs Error: Enter a valid value. Enter number 2: djgfh Error: Enter a valid value. Enter number 2: 300 The sum is equal to 500 > > import Control.Monad (forever) > import Control.Concurrent (threadDelay) > > :t forever forever :: Applicative f => f a -> f b > > :t threadDelay threadDelay :: Int -> IO () > > forever (putStrLn "Hello world Haskell") Hello world Haskell Hello world Haskell Hello world Haskell Hello world Haskell ... ... ... ... -- 1s = 1e6 = 1000000 us delay -- -- > forever (putStrLn "Hello world Haskell" >> threadDelay 1000000) Hello world Haskell Hello world Haskell Hello world Haskell Hello world Haskell Hello world Haskell ^CInterrupted. --- Alternative way --- :{ forever $ do putStrLn "Hello world Haskell" threadDelay 1000000 :} > :{ - forever $ do putStrLn "Hello world Haskell" - threadDelay 1000000 - :} Hello world Haskell Hello world Haskell Hello world Haskell Hello world Haskell ... ... ... ...
It is not possible in a non-pure language. Example in F# (Fsharp).
> let putStrLn s = printfn "%s" s ;; val putStrLn : s:string -> unit > let actions = [putStrLn "hello world" ; putStrLn "hola mundo" ; putStrLn "ola mundo"] ;; hello world hola mundo ola mundo val actions : unit list = [null; null; null] (* It doesn't work. myIF True (putStrLn "Turn on control valve") (putStrLn "Shutdown control valve") *) let myIF cond actionThen actionElse: unit = if cond then actionThen else actionElse ;; - myIF true (putStrLn "Turn on control valve") (putStrLn "Shutdown control valve") ;; Turn on control valve Shutdown control valve val it : unit = () > myIF false (putStrLn "Turn on control valve") (putStrLn "Shutdown control valve") ;; Turn on control valve Shutdown control valve val it : unit = () > // It doesn't work // let myWhen cond fn = if cond then fn else () > myWhen true (putStrLn "Fire missiles") ;; Fire missiles val it : unit = () > myWhen false (putStrLn "Fire missiles") ;; Fire missiles val it : unit = () >
It is possible if the the function application is wrapped in a thunk:
let putStrLn s = fun () -> printfn "%s" s ;; val putStrLn : s:string -> unit -> unit > let actions = [putStrLn "hello world" ; putStrLn "hola mundo" ; putStrLn "ola mundo"] ;; val actions : (unit -> unit) list let runActions actions = (* Haskell Code: runActions :: [IO()] -> IO () runActions ioList = do case ioList of [] -> return () (ioAction:rest) -> do ioAction runActions rest *) let rec runActions ioList = do match ioList with | [] -> () | (ioAction::rest) -> ioAction (); runActions rest ;; - runActions ;; val it : ((unit -> unit) list -> unit) - runActions actions ;; hello world hola mundo ola mundo val it : unit = () > let myIf cond actionThen actionElse : unit = if cond then actionThen () else actionElse () ;; val myIf : cond:bool -> actionThen:unit -> actionElse:unit -> unit > myIf false (putStrLn "Turn on control valve") (putStrLn "Shutdown control valve") ;; Shutdown control valve val it : unit = () > myIf true (putStrLn "Turn on control valve") (putStrLn "Shutdown control valve") ;; Turn on control valve val it : unit = () >
The implementation details can abstracted by defining a type IO.
type IO<'T> = IO of (unit -> 'T) - let runIO (IO thunk) = thunk () ;; val runIO : IO<'a> -> 'a > let putStrLn s: IO<unit> = IO (fun () -> printfn "%s" s) ;; val putStrLn : s:string -> IO<unit> - putStrLn "hello world" ;; val it : IO<unit> > - runIO (putStrLn "hello world") ;; hello world val it : unit = () > - runIO <| putStrLn "hello world" ;; hello world val it : unit = () > let sequence_ (actions: IO<unit> list): IO<unit> = let rec aux xs = match xs with | [] -> () | io::rest -> runIO io ; aux rest IO (fun () -> aux actions) ;; val sequence_ : actions:IO<unit> list -> IO<unit> > - let actionList = [putStrLn "(en) hello world"; putStrLn "(es) hola mundo"; putStrLn "(pt) ola mundo"] ;; val actionList : IO<unit> list = // Creates a new IO actions that will execute each of the IO actions in the list > let action = sequence_ actionList ;; val action : IO<unit> > runIO action ;; (en) hello world (es) hola mundo (pt) ola mundo val it : unit = () > // F# operator (<|) is similar to Haskell operator ($) dollar sign. // To eliminate parenthesis. // - runIO <| sequence_ [putStrLn "(en) hello world"; putStrLn "(es) hola mundo"; putStrLn "(pt) ola mundo"] ;; (en) hello world (es) hola mundo (pt) ola mundo val it : unit = () > let doTimes (n: int) (ioAction: IO<unit>): IO<unit> = let rec aux n = match n with | _ when n < 0 -> failwith "Error: n cannot be negative" | 0 -> () | k -> runIO ioAction ; aux (k - 1) IO (fun () -> aux n) val doTimes : n:int -> ioAction:IO<unit> -> IO<unit> > doTimes 3 (putStrLn "hello world") ;; val it : IO<unit> > - doTimes 3 (putStrLn "hello world") |> runIO ;; hello world hello world hello world val it : unit = () >
1.14.6.2 IO Monad
The IO monad consists of the IO type constructor, the return (unit) function and the (>>=) bind operator implemented for the IO type constructor. It allows build IO actions from smaller IO actions and combine IO actions.
Description | Function | Signature |
---|---|---|
Bind operator | (>>=) | IO a -> (a -> IO b) -> IO b |
Return function | return | a -> IO a |
Operator >> | (>>) | IO a -> IO b -> IO b |
Some IO Primitives:
Console Output Functions | Console Input Functions |
---|---|
putChar :: Char -> IO () | getChar :: Char -> IO () |
putStr :: String -> IO () | |
putStrLn :: String -> IO () | getLine :: IO String |
print :: Show a => a -> IO () | readLn :: Read a => IO a |
Return function
The return function injects a value into an IO action or IO type constructor.
return :: a -> IO a
Bind operator
The bind (>>=) operator extracts the value wrapped by the IO action and pass it to a monadic IO function.
IO a >>= (a -> IO b) :: IO b | | | | | \----> Pass the value wrapped by type constructor to the monadic | function (fn :: a -> IO b) returning a new IO action of type IO b. | \----> Extracts the value (a) wrapped by the IO action ma = mb >>= fn
Example:
:{ dupLine = do line <- getLine putStrLn line :} Prelude M> dupLine haskell rocks haskell rocks Prelude M> {- | The value of IO action getLine is passed to the function putStrLn -} let dupLine2 = getLine >>= putStrLn Prelude M> dupLine2 haskell rocks haskell rocks Prelude M> Prelude M> :t getLine getLine :: IO String Prelude M> :t putStrLn putStrLn :: String -> IO () Prelude M> Prelude M> :t readFile readFile :: FilePath -> IO String Prelude M> :t putStrLn putStrLn :: String -> IO () Prelude M> Prelude M> let showFile file = readFile file >>= putStrLn Prelude M> showFile "/etc/issue" Manjaro Linux \r (\n) (\l) :{ showFile2 file = do content <- readFile file putStrLn content :} Prelude M> showFile2 "/etc/issue" Manjaro Linux \r (\n) (\l)
Bind operator with return:
> return "Print this line" >>= putStrLn Print this line > return "/etc/issue" >>= readFile >>= putStrLn Manjaro Linux \r (\n) (\l)
Operator (>>)
The (>>) operators runs two IO actions sequentially returning the result of the second IO action.
It is defined as
action1 >> action2 = action1 >>= (\_ -> action2)
It is equivalent to in do-notation:
do
action1
action2
Example:
> return 10 >> return 20 :: IO Int 20 > > getLine >> putStrLn "The line is discarded" this line will be discarded The line is discarded > putStrLn "haskell" >> putStrLn "fp" >> putStrLn "rocks" haskell fp rocks > > :t putStrLn "haskell" >> putStrLn "fp" >> putStrLn "rocks" putStrLn "haskell" >> putStrLn "fp" >> putStrLn "rocks" :: IO () :{ action1 = putStrLn "haskell" >> putStrLn "fp" >> putStrLn "rocks" :} > :t action1 action1 :: IO () > action1 haskell fp rocks > -- Equivalent code in do-notation :{ action2 = do putStrLn "haskell" putStrLn "fp" putStrLn "rocks" :} > action2 haskell fp rocks >
Do-notation for the IO monad:
:{ showFile :: IO () showFile = do putStr "Enter a file: " file <- getLine content <- readFile file putStrLn content :} Prelude M> showFile Enter a file: /etc/issue Manjaro Linux \r (\n) (\l)
The Haskell code above like is equivalent to the code below:
:{ showFile :: IO () showFile = putStr "Enter a file: " >>= \ _ -> getLine >>= \ file -> readFile file >>= \ content -> putStrLn content :} Prelude M> showFile Enter a file: /etc/issue Manjaro Linux \r (\n) (\l)
Do-notation example for IO monad
Code:
:{ sumTwoNumbers = do putStr "Enter the first number: " line1 <- getLine putStr "Enter the second number: " line2 <- getLine let x1 = read line1 :: Integer let x2 = read line2 :: Integer let sum = x1 + x2 putStrLn ("The sum is " ++ show sum) return sum :} -- SumTwonumbers dessugarized -- :{ sumTwoNumbers_v2 = putStr "Enter the first number: " >>= \_ -> getLine >>= \line1 -> putStr "Enter the second number: " >>= \_ -> getLine >>= \line2 -> let x1 = read line1 :: Integer in let x2 = read line2 :: Integer in let sum = x1 + x2 in putStrLn ("The sum is " ++ show sum) >>= \_ -> return sum :} -- Do-notation dessugarized simplified with operators (>>) -- :{ sumTwoNumbers_v3 = putStr "Enter the first number: " >> getLine >>= \line1 -> putStr "Enter the second number: " >> getLine >>= \line2 -> let x1 = read line1 :: Integer in let x2 = read line2 :: Integer in let sum = x1 + x2 in putStrLn ("The sum is " ++ show sum) >> return sum :} :{ showResult :: IO Integer -> IO () showResult inputAction = do x <- inputAction putStrLn ( "The result is " ++ show x) :}
Running in the REPL:
> sumTwoNumbers Enter the first number: 100 Enter the second number: 200 The sum is 300 300 > > :t sumTwoNumbers sumTwoNumbers :: IO Integer > > sumTwoNumbers_v2 Enter the first number: 100 Enter the second number: 200 The sum is 300 300 > > sumTwoNumbers_v3 Enter the first number: 100 Enter the second number: 200 The sum is 300 300 > :t sumTwoNumbers_v2 sumTwoNumbers_v2 :: IO Integer > > :t showResult showResult :: IO Integer -> IO () > -- It creates a new IO action. -- > let action = showResult sumTwoNumbers > > action Enter the first number: 100 Enter the second number: 200 The sum is 300 The result is 300 > > :t action action :: IO () > -- The IO actions can be manipulated like values: -- ------------------------------------------------- > :t mapM_ mapM_ :: Monad m => (a -> m b) -> [a] -> m () > > mapM_ putStrLn ["line 0", "line 1", "line2", "line 3"] line 0 line 1 line2 line 3 > > let forEachPrint = mapM_ putStrLn > > :t forEachPrint forEachPrint :: [String] -> IO () > > forEachPrint put putChar putStr putStrLn > forEachPrint ["line 0", "line 1", "line2", "line 3"] line 0 line 1 line2 line 3 > > :t replicateM replicateM :: Monad m => Int -> m a -> m [a] > > let askTwoTimes = replicateM 2 sumTwoNumbers > > askTwoTimes Enter the first number: 100 Enter the second number: 200 The sum is 300 Enter the first number: 300 Enter the second number: 90 The sum is 390 [300,390] >
1.14.6.3 IO Monad in OCaml
The IO monad cannot be implemented in Haskell since it is a primitive type. However by implementing it in OCaml is possible to understand how it works and get some intuition about IO actions and also understand how the monad combinators like (>>), sequence, sequence_ works. This implementation was designed to by as simple as possible.
It is based on the paper: Waddler, Philip. How to Declare an Imperative Language. Page 27. Available at http://homepages.inf.ed.ac.uk/wadler/papers/monadsdeclare/monadsdeclare.ps
let replicate n x = let rec aux count acc = if count = 0 then acc else aux (count - 1) (x::acc) in aux n [] ;; module IO = struct (* Wraps an imperative function like print_string into a thunk *) type 'a io = IO of (unit -> 'a) (* Forces the evaluation of an IO action *) let run: 'a io -> 'a = fun (IO thunk) -> thunk () (* The same as Haskell return :: a -> m a *) let unit: 'a -> 'a io = fun a -> IO ( fun () -> a) let bind: 'a io -> ('a -> 'b io) -> 'b io = fun io_a fn_io -> IO (fun () -> let a = run io_a in run (fn_io a)) let (>>=) = bind (* (>>) :: m a -> m b -> m b (>>) ma mb = ma >>= \_ -> mb *) let (>>) ma mb = ma >>= fun _ -> mb (* Converts an output function into a monadic output IO action *) let lift_output: ('a -> unit) -> ('a -> unit io) = fun output_fn a -> IO (fun () -> output_fn a) (* Converts an input function into a monadic input IO action *) let lift_input: (unit -> 'a) -> 'a io = fun fn_input -> IO fn_input (* fmap derived from IO Monad fmap :: (a -> b) -> IO a -> IO b fmap fn ma = do a <- ma return (fn a) *) let map fn ma = ma >>= fun a -> unit (fn a) (* from: Contro.Monad sequence :: Monad m => [m a] -> m [a] sequence = foldr mcons (return []) where mcons p q = p >>= \x -> q >>= \y -> return (x:y) *) let sequence mlist = let mcons p q = p >>= fun x -> q >>= fun y -> unit (x::y) in List.fold_right mcons mlist (unit []) (* from: Control.Monad *) let sequence_ mlist = List.fold_right (>>) mlist (unit ()) (* from: Control.Monad *) let replicateM_ n ma = sequence_ (replicate n ma) (* from: Control.Monad *) let replicateM n ma = sequence (replicate n ma) (* from: Control.Monad forever :: IO () -> IO *) let rec forever (ma: unit io) = (* let open IO in *) IO ( fun () -> run ma ; let _ = run (forever ma) in () ) (* from: Control.Monad *) let mapM: ('a -> 'b io) -> 'a list -> ('b list) io = fun fn alst -> sequence (List.map fn alst) let mapM_: ('a -> unit io) -> 'a list -> unit io = fun fn alst -> sequence_ (List.map fn alst) (* ----- Primitive IO Functions --------- *) let print_string = lift_output Pervasives.print_string let print_char = lift_output Pervasives.print_char let read_char = lift_input (fun ch -> Pervasives.input_char stdin) let read_line = lift_input Pervasives.read_line let read_int = lift_input Pervasives.read_int (* val input_line : in_channel -> string *) let input_line chan = IO (fun () -> Pervasives.input_line chan) let input_char chan = IO (fun () -> Pervasives.input_char chan) let open_in filename = IO (fun () -> Pervasives.open_in filename) let close_in chan = IO (fun () -> Pervasives.close_in chan) end ;; module IO : sig type 'a io = IO of (unit -> 'a) val run : 'a io -> 'a val unit : 'a -> 'a io val bind : 'a io -> ('a -> 'b io) -> 'b io val ( >>= ) : 'a io -> ('a -> 'b io) -> 'b io val ( >> ) : 'a io -> 'b io -> 'b io val lift_output : ('a -> unit) -> 'a -> unit io val lift_input : (unit -> 'a) -> 'a io val map : ('a -> 'b) -> 'a io -> 'b io val sequence : 'a io list -> 'a list io val sequence_ : 'a io list -> unit io val replicateM_ : int -> 'a io -> unit io val replicateM : int -> 'a io -> 'a list io val forever : unit io -> unit io val mapM : ('a -> 'b io) -> 'a list -> 'b list io val mapM_ : ('a -> unit io) -> 'a list -> unit io val print_string : string -> unit io val print_char : char -> unit io val read_char : char io val read_line : string io val read_int : int io val input_line : in_channel -> string io val input_char : in_channel -> char io val open_in : string -> in_channel io val close_in : in_channel -> unit io end
Tests:
> IO.print_string "\nHello world\n" ;; - : unit IO.io = IO.IO <fun> > let action = IO.print_string "\nHello world\n" ;; val action : unit IO.io = IO.IO <fun> > action ;; - : unit IO.io = IO.IO <fun> > IO.run action ;; Hello world - : unit = () > let open IO in print_string "Hello world" ;; - : unit IO.io = IO.IO <fun> > let open IO in run (print_string "Hello world") ;; Hello world- : unit = () (* echoDup = do c <- getChar putChar c putChar c echoDup = do echoDup = do getChar >>= \c -> getChar >>= \c -> putChar c >>= \_ -> putChar c >> putChar c putChar c *) let echoDup = let open IO in read_char >>= fun c -> print_char c >> print_char c ;; val echoDup : unit IO.io = IO.IO <fun> # echoDup ;; - : unit IO.io = IO.IO <fun> # IO.run echoDup ;; a aa- : unit = () # IO.run echoDup ;; b bb- : unit = () # let make_prompt1 prompt = let open IO in print_string prompt >>= fun _ -> read_line >>= fun line -> print_string "The line is :\n" >>= fun _ -> print_string line >>= fun _ -> unit (String.length line) ;; val make_prompt1 : string -> int IO.io = <fun> # let make_prompt2 prompt = let open IO in print_string prompt >> read_line >>= fun line -> print_string "The line is :\n" >> print_string line >> unit (String.length line) ;; val make_prompt2 : string -> int IO.io = <fun> let do3Times action = let open IO in action >> action >> action ;; val do3Times : 'a IO.io -> 'a IO.io = <fun> # let act = IO.print_string "\nHello world" ;; val act : unit IO.io = IO.IO <fun> # IO.run act ;; Hello world- : unit = () # let act3times = do3Times act ;; val act3times : unit IO.io = IO.IO <fun> # IO.run act3times ;; Hello world Hello world Hello world- : unit = () # # IO.run action1 ;; Tell your name :My name is Jack The line is : My name is Jack- : int = 15 > IO.run (do3Times action1) ;; Tell your name :Jack The line is : JackTell your name :John The line is : JohnTell your name :Caesar The line is : Caesar- : int = 6 # let readTwoNumbers = let open IO in read_int >>= fun a -> read_int >>= fun b -> unit (2 *a + b) ;; val readTwoNumbers : int IO.io = IO.IO <fun> # IO.replicateM_ 5 (IO.print_string "\nHello World\n") ;; - : unit IO.io = IO.IO <fun> # IO.run (IO.replicateM_ 5 (IO.print_string "\nHello World\n")) ;; Hello World Hello World Hello World Hello World Hello World - : unit = () # # IO.run IO.read_int ;; 232 - : int = 232 # IO.replicateM 4 IO.read_int ;; - : int list IO.io = IO.IO <fun> # IO.run (IO.replicateM 4 IO.read_int) ;; 2 43 34 100 - : in let echoLine = let open IO in read_line >>= fun line -> print_string line ;; val echoLine : unit IO.io = IO.IO <fun> # IO.run echoLine ;; Hello world Hello world- : unit = () # # IO.forever echoLine ;; - : unit IO.io = IO.IO <fun> # let echoLoop = IO.forever echoLine ;; val echoLoop : unit IO.io = IO.IO <fun> # IO.run echoLoop ;; line1 line1 line2 line2 line3 line3 (* Hit Ctrl + D *) Exception: End_of_file. # IO.mapM ;; - : ('a -> 'b IO.io) -> 'a list -> 'b list IO.io = <fun> # IO.mapM IO.print_string ["a"; "b"; "c"; "d"] ;; - : unit list IO.io = IO.IO <fun> # # IO.run (IO.mapM_ IO.print_string ["a"; "b"; "c"; "d"] );; abcd- : unit = () # let open IO in replicateM_ 6 (print_string "\ntest") |> run ;; test test test test test test- : unit = () #
1.14.6.4 See also
- A Gentle Introduction to Haskell: IO
- A Gentle Introduction to Haskell: About Monads
- IO inside - HaskellWiki
- Haskell I/O Tutorial
- CS 209 - Functional Programming
- Waddler, Philip. How to Declare an Imperative Language. Page 27. Available at http://homepages.inf.ed.ac.uk/wadler/papers/monadsdeclare/monadsdeclare.ps
1.14.7 State Monad
1.14.7.1 Overview
The state monad represents stateful in purely functional way.
1.14.7.2 State monad in Haskell
The state monad in Haskell 2010 standard is not implemented in a simple way like in Haskell 98 which breaks legacy codes from papers and old books based on the 98 standards. Now it is implemented as a combination of StateT monad transformer and Identity monad. Despite the implementation changes the behavior of State monad is the same as in the old one.
type State s = StateT s Data.Functor.Identity.Identity -- Defined in ‘Control.Monad.Trans.State.Lazy’ --- Old Implementation: --- newtype State s a = State { runState :: s -> (a, s) }
It is equivalent to:
type State s a = s -> (a, s)
State tranformer function | ----+------ type State s a = s -> (a, s) | | | | | +---> Next State | | | +------> Current Output | +------------> Current State state transformer = s -> (a, s)
State transformer:
stateTransformer :: current state -> (output, next state) current +---------------+ state | State | Next State ---> + +--------> | Transformer | +---------+-----+ | | \ / State output StateFn :: State s a ==> s -> (a, s) +---------+ +-----------+ +----------+ +----------+ S0 | | S1 | | S2 | | S3 | | S4 ... ---->+ StateFn +----->+ StateFn +----->+ StateFn +------>+ StateFn +-----> | | | | | | | | +---+-----+ +-----+-----+ +----+-----+ +----+-----+ | (a1, s1) | (a2, s2) | (a3, s3) | | | | | \ / \ / \ / \ / a1 a2 a3 a4 (a1, s1) = runState StateFn s0 (a2, s2) = runState StateFn s1 (a3, s3) = runState StateFn s2 ...
state
Wraps a state transformer function of type s -> (a, s)
into a State
type constructor.
state :: MonadState s m => (s -> (a, s)) -> m a >>> import Control.Monad.State >>> let fnSt = (state $ \s -> (s * 3, s + 2) ) :: State Int Int >>> :t fnSt fnSt :: State Int Int >>> >>> runState fnSt 1 (3,3) >>> runState fnSt 0 (0,2) >>> runState fnSt 2 (6,4) {- In the old implementation it was: let fnSt = (State $ \s -> (s * 3, s + 2)) :: State Int Int It doesn't work anymore. -} >>> let fnSt = (State $ \s -> (s * 3, s + 2) ) :: State Int Int Prelude System.Directory System.Process Control.Monad.State| <interactive>:223:13: Not in scope: data constructor ‘State’ Perhaps you meant one of these: ‘StateT’ (imported from Control.Monad.State), variable ‘state’ (imported from Control.Monad.State) >>>
runState
Applies a state transformer type (State s a) to a current state and returns a new state and an output.
runState :: State s a -> s -> (a, s)
evalState
Similar to runState, but returns only the output.
evalState :: State s a -> s -> a evalState = fst . runState
execState
Similar to runState, but returns only the next state.
execState :: State s a -> s -> s execState = snd . runState
return
Sets the output regardless of the current state:
return a = State $ \s -> (a, s) >>> let st = return 10 :: State Int Int >>> runState st 0 (10,0) >>> runState st 1 (10,1) >>> runState st 2 (10,2) >>> >>> runState (return 10) 0 (10,0) >>> runState (return 10) 1 (10,1) >>> runState (return 10) 2 (10,2) >>> runState (return 10) 3 (10,3) >>> runState (return 10) 4
bind
Note: This is the old implementation with meaningful names. But with the same behavior as the new implementation.
(>>=) :: State s a -> (a -> State s b) -> State s b stateFn >>= stateMaker = State $ \oldState -> let (result, newState) = runState stateFn oldState in runState (stateMaker result) newState
put
Set a state ignoring the output.
put :: MonadState s m => s -> m () -- Old implementation: -- put :: s -> State s () put s = State (\ _ -> ((), s)) >>> runState (put 10) 0 ((),10) >>> runState (put 10) 1 ((),10) >>> runState (put 10) 2 ((),10) >>> runState (put 10) 3 ((),10) >>> execState (put 10) 0 10 >>> execState (put 10) 1 10 >>> execState (put 10) 2 10 >>> execState (put 10) 3 10 >>>
get
Get the current state.
get :: MonadState s m => m s -- Old implementation: -- get :: State s s get = State (\s -> (s, s)) >>> runState get 0 (0,0) >>> runState get 1 (1,1) >>> runState get 2 (2,2) >>> runState get 3 (3,3)
withstate
withState f m executes action m on a state modified by applying f. (Documentation)
withState :: (s -> s) -> State s a -> State s a withState f m = modify f >> m
fmap
Returns a new state transformer applying a function to the output of the old state transformer.
Note: This the old implementation without StateT. However it still works in the same way and still describes what the State functor does.
instance Functor (State s) where -- Applies a function to the state output. -- -- fmap :: (a -> b) -> F a -> F b -- -- fmap :: (a -> b) -> State s a -> State s b fmap f fns = State $ \oldState -> let (output, newState) = runState fns oldState in (f output, newState)
Example:
>>> import Control.Monad.State >>> >>> :show language base language is: Haskell2010 with the following modifiers: -XNoDatatypeContexts -XNondecreasingIndentation >>> >>> :info State type State s = StateT s Data.Functor.Identity.Identity -- Defined in ‘Control.Monad.Trans.State.Lazy’ -- Check type signature -- >>> :t state state :: MonadState s m => (s -> (a, s)) -> m a >>> >>> :t evalState evalState :: State s a -> s -> a >>> >>> :t evalState evalState :: State s a -> s -> a >>> >>> :t runState runState :: State s a -> s -> (a, s) >>> >>> :t put put :: MonadState s m => s -> m () >>> >>> :t get get :: MonadState s m => m s >>> -- Code block to paste in the GHCI repl -- -- >>> let postincrement = do { x <- get; put (x+1); return x } >>> runState postincrement 1 (1,2) >>> runState postincrement 2 (2,3) >>> runState postincrement 3 (3,4) >>> :set +m :{ let stFn :: Int -> (Int, Int) stFn = \ currentState -> let output = 2 * currentState in let nextState = currentState + 1 in (output, nextState) :} >>> :t stFn stFn :: Int -> (Int, Int) >>> >>> stFn 1 -- S0 = 1 --> S1 = 2, output = 2 (2,2) >>> stFn 2 -- S1 = 1 --> S2 = 3, output = 4 (4,3) >>> stFn 3 -- S2 = 3 --> S3 = 4, output = 6 (6,4) >>> stFn 4 (8,5) >>> stFn 5 (10,6) >>> {- Now let's wrap inside the State type -} :{ let stateFn1 :: State Int Int stateFn1 = state $ \ st -> (2 * st, st + 1) :} >>> :t stateFn1 stateFn1 :: State Int Int >>> >>> runState stateFn1 1 (2,2) >>> runState stateFn1 2 (4,3) >>> runState stateFn1 3 (6,4) >>> runState stateFn1 4 (8,5) >>> runState stateFn1 5 (10,6) >>> >>> execState stateFn1 5 --- snd (10, 6) 6 >>> evalState stateFn1 5 ---- fst (10, 6) 10 >>> >>> runState (withState (\s -> s + 3) stateFn1) 1 (8,5) >>> runState (withState (\s -> s + 3) stateFn1) 2 (10,6) >>> runState (withState (\s -> s + 3) stateFn1) 3 (12,7) >>> runState (withState (\s -> s + 3) stateFn1) 4 (14,8) >>> runState (withState (\s -> s + 3) stateFn1) 5 (16,9) >>> type StState = Int type StOutput = Int :{ let stateFn2 :: State StState StOutput stateFn2 = state $ \ st -> (2 * st, st + 1) :} >>> :t stateFn2 stateFn2 :: State StState StOutput >>> >>> runState stateFn2 0 (0,1) >>> runState stateFn2 1 (2,2) >>> runState stateFn2 2 (4,3) >>> runState stateFn2 3 (6,4) >>> runState stateFn2 4 (8,5) >>> :t stateFn2 stateFn2 :: State StState StOutput >>> >>> :t runState stateFn2 4 runState stateFn2 4 :: (StOutput, StState) >>> :{ let stateFn3 :: State Int Int stateFn3 = do currentState <- get put (currentState + 1) --- put $ currentState + 1 return (2 * currentState) :} >>> :t stateFn3 stateFn3 :: State Int Int >>> >>> runState stateFn3 0 (0,1) >>> runState stateFn3 1 (2,2) >>> runState stateFn3 2 (4,3) >>> runState stateFn3 3 (6,4) >>> runState stateFn3 4 (8,5) >>> runState stateFn3 5 (10,6) >>> {- Do-notation dessugarized cs : Stands for current state. -} :{ let stateFn4 :: State Int Int stateFn4 = get >>= \ cs -> put (cs + 1) >>= \ _ -> return (2 * cs) :} >>> runState stateFn4 0 (0,1) >>> runState stateFn4 1 (2,2) >>> runState stateFn4 2 (4,3) >>> runState stateFn4 3 (6,4) >>> runState stateFn4 4 (8,5) >>> runState stateFn4 5 (10,6) >>> >>> runState (fmap (\x -> x + 3) stateFn4) 0 -- 3 = (\x -> x + 3) 0 (3,1) >>> runState (fmap (\x -> x + 3) stateFn4) 1 -- 5 = (\x -> x + 3) 2 (5,2) >>> runState (fmap (\x -> x + 3) stateFn4) 2 -- 7 = (\x -> x + 4) (7,3) >>> runState (fmap (\x -> x + 3) stateFn4) 3 (9,4) >>> runState (fmap (\x -> x + 3) stateFn4) 4 (11,5) >>> runState (fmap (\x -> x + 3) stateFn4) 5 (13,6) >>> :t fmap fmap :: Functor f => (a -> b) -> f a -> f b >>> >>> let stateFnMap = fmap (\x -> x + 3) stateFn3 >>> :t stateFnMap stateFnMap :: StateT Int Data.Functor.Identity.Identity Int >>> >>> runState stateFnMap 0 (3,1) >>> runState stateFnMap 1 (5,2) >>> runState stateFnMap 2 (7,3) >>> runState stateFnMap 3 (9,4) >>> runState stateFnMap 4 (11,5) >>>
Example from the book Learn You a Haskell:
Simulating a stack:
import Control.Monad.State type Stack = [Int] -- Each code block must be pasted into the repl (ghci) -- :set +m :{ let pop :: State Stack Int pop = state $ \(x:xs) -> (x, xs) -- pop = State $ \(x:xs) -> (x,xs) (It doesn't work anymore in this way). :} >>> :t pop pop :: State Stack Int >>> :{ let push :: Int -> State Stack () push a = state $ \xs -> ((), a:xs) :} >>> :t push push :: Int -> State Stack () >>> :{ let stackManip = do push 3 a <- pop pop :} >>> :t stackManip stackManip :: StateT Stack Data.Functor.Identity.Identity Int >>> >>> runState pop [1, 2, 3, 4] (1,[2,3,4]) >>> runState pop [2, 3, 4] (2,[3,4]) >>> runState pop [3, 4] (3,[4]) >>> runState pop [4] (4,[]) >>> runState pop [] *** Exception: <interactive>:20:19-36: Non-exhaustive patterns in lambda >>> evalState pop [1, 2, 3, 4] 1 >>> evalState pop [2, 3, 4] 2 >>> execState pop [1, 2, 3, 4] [2,3,4] >>> execState pop [2, 3, 4] [3,4] >>> >>> runState (push 3) [4, 5, 6] ((),[3,4,5,6]) >>> runState (push 10) [1, 4, 5, 6] ((),[10,1,4,5,6]) >>> >>> runState stackManip [5,8,2,1] (5,[8,2,1]) >>> {- stackStuff :: State Stack () stackStuff = do a <- pop if a == 5 then push 5 else do push 3 push 8 -} :{ let stackStuff :: State Stack () stackStuff = do a <- pop if a == 5 then push 5 else do push 3 push 8 :} >>> :t stackStuff stackStuff :: State Stack () >>> >>> runState stackStuff [9,0,2,1,0] ((),[8,3,0,2,1,0]) >>> -- push a = State $ \xs -> ((),a:xs)
Random numbers:
>>> import Control.Monad.State >>> import System.Random >>> {- randomSt :: (RandomGen g, Random a) => State g a randomSt = State random -} >>> let randomSt = state random >>> >>> :t randomSt randomSt :: (MonadState s m, RandomGen s, Random a) => m a >>> >>> :t randomSt randomSt :: (MonadState s m, RandomGen s, Random a) => m a >>> {- threeCoins :: State StdGen (Bool,Bool,Bool) threeCoins = do a <- randomSt b <- randomSt c <- randomSt return (a,b,c) -} :{ let threeCoins :: State StdGen (Bool,Bool,Bool) threeCoins = do a <- randomSt b <- randomSt c <- randomSt return (a,b,c) :} >>> :t threeCoins threeCoins :: State StdGen (Bool, Bool, Bool) >>> >>> runState threeCoins (mkStdGen 33) ((True,False,True),680029187 2103410263) >>> >>> runState threeCoins (mkStdGen 33) ((True,False,True),680029187 2103410263) >>> >>> import Data.List (unfoldr) >>> >>> :t unfoldr unfoldr :: (b -> Maybe (a, b)) -> b -> [a] >>> {- Generates an infinite sequence of state output -} :{ let stateSeqOutput stateFn state0 = unfoldr ( \s -> let (out, ns) = runState stateFn s in Just (out, ns)) state0 :} >>> :t stateSeqOutput stateSeqOutput :: State b a -> b -> [a] >>> >>> take 4 $ stateSeqOutput threeCoins (mkStdGen 33) [(True,False,True),(True,True,True),(False,False,False),(True,False,True)] >>> >>> mapM_ print $ take 10 $ stateSeqOutput threeCoins (mkStdGen 33) (True,False,True) (True,True,True) (False,False,False) (True,False,True) (True,False,True) (True,True,False) (False,False,True) (False,False,False) (True,True,False) (True,True,True) >>>
Example: Fibonacci Sequence
The Fibonacci sequence is defined by the rule.
a[n+2] = a[n+1] + a[n] 0 1 1 = 1 + 0 2 = 1 + 1 3 = 2 + 1 5 = 3 + 2 8 = 5 + 3 ... +-----+ +----+ +----+ S0 -->+ fn +-----------> | fn +---------->| fn |------> .... (0, 1) +--+--+ S1 +-+--+ S2 +-+--+ S3 (2, 3) | (1, 0 + 1) | (1, 2) | | (1, 1) | | \ / \ / \ / output = 0 + 1 output = 1 + 1 output = 1 + 2 = 1 = 2 = 3
It needs to keep track of the two last numbers.
import Control.Monad.State -- Load from a file -- fibgen :: State (Int, Int) Int fibgen = do a, b <- get let c = a + b put (b, c) -- set the new state return c -- Repl friendly version -- :{ let fibgen :: State (Int, Int) Int fibgen = do (a, b) <- get let c = a + b put (b, c) -- set the new state return c :} >>> :t fibgen fibgen :: State (Int, Int) Int >>> >>> runState fibgen (0, 1) (1,(1,1)) >>> runState fibgen (1, 1) (2,(1,2)) >>> runState fibgen (1, 2) (3,(2,3)) >>> runState fibgen (2, 3) (5,(3,5)) >>> runState fibgen (3, 5) (8,(5,8)) >>> runState fibgen (5, 8) (13,(8,13)) >>> >>> evalState fibgen (5, 8) 13 >>> execState fibgen (5, 8) (8,13) >>> :{ let fibgen2 :: State (Int, Int) Int fibgen2 = state $ \ (a, b) -> let c = a + b in (c, (b, c)) :} >>> runState fibgen2 (0, 1) (1,(1,1)) >>> runState fibgen2 (1, 1) (2,(1,2)) >>> runState fibgen2 (1, 2) (3,(2,3)) >>> runState fibgen2 (2, 3) (5,(3,5)) >>> runState fibgen2 (3, 5) (8,(5,8)) >>> runState fibgen2 (5, 8) (13,(8,13)) >>> {- Generating the state sequence -} >>> import Data.List (unfoldr) >>> >>> :t unfoldr unfoldr :: (b -> Maybe (a, b)) -> b -> [a] >>> :{ let fibseq = unfoldr (\s -> let (out, ns) = runState fibgen s in Just (out, ns)) (0, 1) :} >>> :t fibseq fibseq :: [Int] >>> >>> take 20 fibseq [1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946] >>>
1.14.7.3 State monad in OCaml
Implementation:
(* stfn - Stands for state transformer *) module State = struct type ('s, 'a) state = ST of ('s -> 'a * 's) (* Runs the state transformer runState *) let run (ST stfnt) s = stfnt s (* Gets only the result and discards the the next state. evalState *) let eval stfn s = fst (run stfn s) (* Gets only the next state and drops the result execState *) let exec stfn s = snd (run stfn s) let put s = ST (fun _ -> ((), s)) let get = ST (fun s -> (s, s)) (* return a = State $ \s -> (a, s) *) let unit a = ST (fun s -> (a, s)) let bind stfn stfnMaker = ST ( fun currentState -> let (result, newState) = run stfn currentState in run (stfnMaker result) newState ) (* fmap *) let map fn stfn = ST (fun currentState -> let (result, newState) = run stfn currentState in (fn result, newState) ) let (>>=) = bind let (<$>) = map let (>>) ma mb = ma >>= fun _ -> mb let sequence mlist = let mcons p q = p >>= fun x -> q >>= fun y -> unit (x::y) in List.fold_right mcons mlist (unit []) (* Applicative Functor - Haskell <$> *) let (<*>) m_fn ma = m_fn >>= fun fn -> ma >>= fun a -> unit (fn a) let liftM2 fn ma mb = ma >>= fun a -> mb >>= fun b -> unit (fn a b) let liftM3 fn ma mb mc = ma >>= fun a -> mb >>= fun b -> mc >>= fun c -> unit (fn a b c) let mapM fn alst = sequence (List.map fn alst) end ;; module State : sig type ('s, 'a) state = ST of ('s -> 'a * 's) val run : ('a, 'b) state -> 'a -> 'b * 'a val eval : ('a, 'b) state -> 'a -> 'b val exec : ('a, 'b) state -> 'a -> 'a val put : 'a -> ('a, unit) state val get : ('a, 'a) state val unit : 'a -> ('b, 'a) state val bind : ('a, 'b) state -> ('b -> ('a, 'c) state) -> ('a, 'c) state val map : ('a -> 'b) -> ('c, 'a) state -> ('c, 'b) state val ( >>= ) : ('a, 'b) state -> ('b -> ('a, 'c) state) -> ('a, 'c) state val ( <$> ) : ('a -> 'b) -> ('c, 'a) state -> ('c, 'b) state val ( >> ) : ('a, 'b) state -> ('a, 'c) state -> ('a, 'c) state val sequence : ('a, 'b) state list -> ('a, 'b list) state val ( <*> ) : ('a, 'b -> 'c) state -> ('a, 'b) state -> ('a, 'c) state val liftM2 : ('a -> 'b -> 'c) -> ('d, 'a) state -> ('d, 'b) state -> ('d, 'c) state val liftM3 : ('a -> 'b -> 'c -> 'd) -> ('e, 'a) state -> ('e, 'b) state -> ('e, 'c) state -> ('e, 'd) state val mapM : ('a -> ('b, 'c) state) -> 'a list -> ('b, 'c list) state end #
Tests:
Basic Example:
let stFn = let open State in ST (fun s -> (2 * s, s + 1)) ;; val stFn : (int, int) State.state = State.ST <fun> # State.run stFn 1 ;; - : int * int = (2, 2) # State.run stFn 2 ;; - : int * int = (4, 3) # State.run stFn 3 ;; - : int * int = (6, 4) # State.run stFn 4 ;; - : int * int = (8, 5) # State.run stFn 5 ;; - : int * int = (10, 6) # State.run stFn 6 ;; - : int * int = (12, 7) # # State.eval stFn 6 ;; - : int = 12 # # State.exec stFn 6 ;; - : int = 7 # # let stFn2 = let open State in map (fun x -> x + 3) stFn ;; val stFn2 : (int, int) State.state = State.ST <fu # State.run stFn2 1 ;; - : int * int = (5, 2) # State.run stFn2 2 ;; - : int * int = (7, 3) # State.run stFn2 3 ;; - : int * int = (9, 4) # State.run stFn2 4 ;; - : int * int = (11, 5) # State.run stFn2 5 ;; - : int * int = (13, 6) # let fn x = x + 3 ;; val fn : int -> int = <fun> # State.run (State.map fn stFn) 1 ;; - : int * int = (5, 2) # State.run (State.map fn stFn) 2 ;; - : int * int = (7, 3) # State.run (State.map fn stFn) 3 ;; - : int * int = (9, 4) # State.run (State.map fn stFn) 4 ;; - : int * int = (11, 5) # (* Haskell Code: :{ let stateFn3 :: State Int Int stateFn3 = do currentState <- get put (currentState + 1) --- put $ currentState + 1 return (2 * currentState) :} ---------------------------------------- *) let stFn3 = let open State in get >>= fun cs -> put (cs + 1) >>= fun _ -> unit (2 * cs) ;; val stFn3 : (int, int) State.state = State.ST <fun> let stFn4 = let open State in get >>= fun cs -> put (cs + 1) >> unit (2 * cs) ;; val stFn4 : (int, int) State.state = State.ST <fun> # State.run stFn3 1 ;; - : int * int = (2, 2) # State.run stFn3 2 ;; - : int * int = (4, 3) # State.run stFn3 3 ;; - : int * int = (6, 4) # State.run stFn3 4 ;; - : int * int = (8, 5) # State.run stFn3 5 ;; - : int * int = (10, 6) # # State.run stFn4 1 ;; - : int * int = (2, 2) # State.run stFn4 2 ;; - : int * int = (4, 3) # State.run stFn4 3 ;; - : int * int = (6, 4) # State.run stFn4 4 ;; - : int * int = (8, 5) # State.run stFn4 5 ;; - : int * int = (10, 6) #
Simulating a Stack:
(* type Stack = [Int] *) type stack = int list (* With type signature *) let pop: (stack, int) State.state = let open State in ST ( fun (x::xs) -> (x, xs) ) ;; val pop : (stack, int) State.state = State.ST <fun> (* Without type signature *) let pop = let open State in ST (fun (x::xs) -> (x, xs)) ;; let push: int -> (stack, unit) State.state = let open State in fun a -> ST ( fun xs -> ((), a::xs) ) ;; val push : int -> (stack, unit) State.state = <fun> (* :{ let stackManip = do push 3 a <- pop pop :} *) let stackManip = let open State in push 3 >> pop >>= fun a -> pop ;; val stackManip : (stack, int) State.state = State.ST <fun> # State.run pop [1; 2; 3; 4] ;; - : int * int list = (1, [2; 3; 4]) # State.run pop [2; 3; 4] ;; - : int * int list = (2, [3; 4]) (* :{ let stackStuff :: State Stack () stackStuff = do a <- pop if a == 5 then push 5 else do push 3 push 8 :} *) let stackStuff = let open State in pop >>= fun a -> if a = 5 then push 5 else ( push 3 >> push 8 ) ;; val stackStuff : (stack, unit) State.state = State.ST <fun> # State.run stackStuff [9; 0; 2; 1; 0] ;; - : unit * stack = ((), [8; 3; 0; 2; 1; 0]) #
1.14.8 Reader Monad
1.14.8.1 Overview
A common problem in software development is propagate configuration, or global immutable state throughout the code. For instance, modular arithmetic needs the modulus configuration; numerical code needs the tolerance and maximum number of iterations and a web server needs at least the database configuration and the directory which contains static files.
The problem of propagating and supporting multiple configurations (aka run-time preferences) is known as the configuration problem.
In many programming languages, a naive solution to the configuration problem would be global variables, however this approach doesn't allow multiple sets of configurations to coexist and also a global variable may be changed by any part of the program make it unpredictable and hard to understand. An alternative solution to this problem is to bundle all configuration parameters into a single configuration parameter and pass it around explicitly as a function argument or pass the configuration bundle implicitly with the Reader monad.
1.14.8.2 Reader Monad
The reader monad solves the configuration problem by making the configuration (aka enviroment) or global immutable state implicit and hiding it.
As the new implementation of the Reader monad is based on monad transformer, this section will use a more simple implementation similar to the old one for the sake of making the concept easier to understand.
- Too see an example with Reader monad transformer and databases check out Databases - HDBC package.
- File: src/readerMonad.hs
Signaures:
Signature | Description | |
---|---|---|
Reader r a | - | Encapsulates a function or computation from a to b. |
Reader | (a -> b) -> Reader r a | |
runReader | Reader r a -> r -> a | Run computation encapsulated by Reader r a applying it to the configuration r. |
return | a -> (Reader r) a | Returns a constant function wrapped by Reader that always returns a |
,no matter the value r. | ||
(>>=) | a -> (Reader r) b -> (Reader r) b | Monad bind function. |
fmap | (a -> b) -> (Reader r) a -> (Reader r) b | Apply a function (a -> b) to the result of computation Reader r a. |
ask | Reader r r | Read environment or configuration. Ask wraps an identity function. |
local | (r -> r) -> Reader r a -> Reader r a | Modify environment by applying a function to it. |
newtype Reader r a = Reader {runReader :: r -> a} instance Functor (Reader r) where -- -- fmap is the function compsition between function fn and -- the function wrapped by the reader monad. -- -- fmap :: (a -> b) -> (Reader r) a -> (Reader r) b -- fmap fn (Reader rToA) = Reader $ \ r -> fn $ rToA r instance Applicative (Reader r) where {- | pure :: Applicative f => a -> f a pure :: a -> (Reader r) a -} pure a = Reader $ \_ -> a {- | (<*>) :: Applicative f => f (a -> b) -> f a -> f b (<*>) :: Reader r (a -> b) -> (Reader r) a -> (Reader r) b -} (Reader fn) <*> (Reader rToA) = Reader $ (\r -> let a = rToA r in let fAtoB = fn r in fAtoB a ) instance Monad (Reader r) where {- | return :: a -> (Reader r) a -} return a = Reader $ \ _ -> a {- | (>>=) :: (Monad m) => m a -> (a -> m b) -> m b (Reader r) a >>= (a -> (Reader r) b) -> (Reader r) b -} (Reader rToA) >>= fn = Reader $ \ r -> let a = rToA r in runReader (fn a) r {- | Read environment, aka configuration. -} ask :: Reader r r ask = Reader (\ r -> r) local :: (r -> r) -> Reader r a -> Reader r a local fn (Reader rToA) = Reader $ \ r -> rToA (fn r)
1.14.8.3 Testing old Reader monad code
Load the code in the REPL:
> > :load src/readerMonad.hs [1 of 1] Compiling Main ( src/readerMonad.hs, interpreted ) Ok, modules loaded: Main.
- Encapsulating computation with reader
> :t Reader Reader :: (r -> a) -> Reader r a > {- The function _return_ implementation for Read monad takes a value and returns a constant function which, regardless of the input, always returns the same value. -} > let x = return 10 :: Reader Int Int x :: Reader Int Int > > runReader x 15 10 it :: Int > runReader x 25 10 it :: Int > runReader x 35 10 it :: Int > let greetUser1 user = "Hello " ++ user ++ "! Welcome to the FP world!" > greetUser1 "John" "Hello John! Welcome to the FP world!" it :: [Char] > :{ greetUser2 :: Reader String String greetUser2 = Reader (\ user -> "Hello " ++ user ++ "! Welcome to the FP world!" ) :} > runReader greetUser2 "Beowulf" "Hello Beowulf! Welcome to the FP world!" it :: String > :{ greetUser3 :: Reader String String greetUser3 = do user <- ask return $ "Hello " ++ user ++ "! Welcome to the FP world!" :} > runReader greetUser3 "Beowulf" "Hello Beowulf! Welcome to the FP world!" it :: String > :{ talkToUser :: Reader String (IO()) talkToUser = do user <- ask msga <- greetUser2 msgb <- greetUser3 return $ do putStrLn $ "User name is " ++ user putStrLn msga putStrLn msgb :} > runReader talkToUser "John" User name is John Hello John! Welcome to the FP world! Hello John! Welcome to the FP world! it :: () > -- Apply the function length to the output of greetUser3 computation -- > runReader greetUser3 "John" "Hello John! Welcome to the FP world!" it :: String > length $ runReader greetUser3 "John" 36 it :: Int > > runReader (fmap length greetUser2) "John" 36 it :: Int > runReader (fmap length greetUser3) "John" 36 it :: Int >
1.14.8.4 Example: Configuration problem example - Arithmetic
The goal of this example is to perform mudular arithmetic computations to be used with multiple moduli hiding the modulus parameter as much as possible.
Example 1: Configuration problem with parameter passing approach.
The configuration modulus which all computations depends on is passed as function argument instead of being passed as a global value or variable. Example taken from - Functional Pearl: Implicit Configurations http://okmij.org/ftp/Haskell/tr-15-04.pdf
> > :load src/readerMonad.hs [1 of 1] Compiling Main ( src/readerMonad.hs, interpreted ) Ok, modules loaded: Main. > add1 m a b = mod (a + b) m add1 :: Integral a => a -> a -> a -> a > > mul1 m a b = mod (a * b) m mul1 :: Integral a => a -> a -> a -> a > > test1 m a b = add1 m (mul1 m a a) (mul1 m b b) test1 :: Integral a => a -> a -> a -> a > -- Modulus set to 120 -- > add1 120 975 873 48 it :: Integral a => a > > mul1 120 975 873 15 it :: Integral a => a > > test1 120 975 873 114 it :: Integral a => a > -- Modulus set to 327 -- > add1 327 975 873 213 it :: Integral a => a > > mul1 327 975 873 321 it :: Integral a => a > > test1 327 975 873 255 it :: Integral a => a >
Example 2: Configuration problem with parameter passing with Reader monad.
This approach allows the computation results to be reused easily with multiple modulus or configurations. In addition, new computations can be defined from previous computations with implicit modulus parameter.
> > :load src/readerMonad.hs [1 of 1] Compiling Main ( src/readerMonad.hs, interpreted ) Ok, modules loaded: Main. -- Reader a a => Reader [modulus] [result] -- :{ add2 :: Integral a => a -> a -> Reader a a add2 a b = Reader (\m -> mod (a + b) m) :} :{ mul2 :: Integral a => a -> a -> Reader a a mul2 a b = do m <- ask return $ mod (a * b) m :} -- The configuration modulus is passed implicitly. -- :{ test2 :: Integral a => a -> a -> Reader a a test2 a b = do x <- mul2 a a y <- mul2 b b s <- add2 x y return s :} -- The result of the computations r1, r2 and r3 can be reused with -- multiple modulus or multiple configurations. -- > r1 = add2 975 873 r1 :: Integral a => Reader a a > runReader r1 120 48 it :: Integral a => a > runReader r1 327 213 it :: Integral a => a > > map (runReader r1) [120, 327, 28, 17] [48,213,0,12] it :: Integral b => [b] > > r2 = mul2 975 873 r2 :: Integral a => Reader a a > > r3 = test2 975 873 r3 :: Integral a => Reader a a > > map (runReader r3) [127, 327, 28, 17, 97] [32,255,22,4,25] it :: Integral b => [b] >
Example 4: The modular arithmetic can be made less verbose if an instance of type class Num is defined for the type synonym Modulus.
- Note: The code below works with Control.Monad.Read too. Just
replace the
:load src/readerMonad.hs
withimport Control.Monad.Read
.
> > :load src/readerMonad.hs [1 of 1] Compiling Main ( src/readerMonad.hs, interpreted ) Ok, modules loaded: Main. :set -XRankNTypes type Modulus m = forall a. Integral a => Reader a a :{ normalize :: Integral a => a -> Reader a a normalize x = do m <- ask return $ mod x m :} -- Modular arithmetic equality -- :{ (===) :: (Integral a) => Modulus a -> Modulus a -> Reader a Bool (===) ma mb = do a <- ma b <- mb return $ a == b :} {- > :info Num class Num a where (+) :: a -> a -> a (-) :: a -> a -> a (*) :: a -> a -> a negate :: a -> a abs :: a -> a signum :: a -> a fromInteger :: Integer -> a {-# MINIMAL (+), (*), abs, signum, fromInteger, (negate | (-)) #-} -} :{ instance (Integral a) => Num (Reader a a) where fromInteger x = normalize (fromIntegral x) ma + mb = do a <- ma b <- mb normalize (a + b) ma - mb = do a <- ma b <- mb normalize (a - b) ma * mb = do a <- ma b <- mb normalize (a * b) signum = error "Not implemented" abs = error "Not implemented" :} {- | --------- Tests ----------- -} > let x = 38 :: Modulus a x :: Integral a => Reader a a > let y = 23 :: Modulus a y :: Integral a => Reader a a > runReader x 15 8 it :: Integral a => a > runReader y 15 8 it :: Integral a => a > > m = 38 === 23 m :: Integral a => Reader a Bool > > runReader m 15 True it :: Bool > > runReader (8 === 3) 5 True it :: Bool > > let x = 975 + 873 :: Integral a => Reader a a x :: Integral a => Reader a a > > runReader x 120 48 it :: Integral a => a > runReader x 327 213 it :: Integral a => a > > let r1 = 975 + 873 :: Modulus a r1 :: Integral a => Reader a a > > runReader r1 120 48 it :: Integral a => a > runReader r1 327 213 it :: Integral a => a > :{ test3 :: Modulus a -> Modulus a -> Modulus a test3 a b = a * a + b * b :} > let r3 = test3 975 873 r3 :: Integral a => Reader a a > > runReader r3 120 114 it :: Integral a => a > > runReader r3 327 255 it :: Integral a => a > > map (runReader r3) [127, 327, 28, 17, 97] [32,255,22,4,25] it :: Integral b => [b] >
1.14.8.5 References
- Control.Monad.Read Documentation https://hackage.haskell.org/package/mtl-2.2.1/docs/Control-Monad-Reader.html
- Oleg Kiselyov and Chung-Chien Shan - Functional Peral: Implicit Configturation or Type Classes Reflect the Value of Types - http://okmij.org/ftp/Haskell/tr-15-04.pdf
- Hakkell Wiki - Global Variable - https://wiki.haskell.org/Global_variables
- Joachim Bach. A Solution to the Configuration Problem in Haskell - https://www.joachim-breitner.de/blog/443-A_Solution_to_the_Configuration_Problem_in_Haskell
Additional Readings
Solutions to Configuration Problem
- The reflection package - https://hackage.haskell.org/package/reflection
Global Variables
- Why global variables are evil - http://www.learncpp.com/cpp-tutorial/4-2a-why-global-variables-are-evil/
- Global Variables are Bad - http://wiki.c2.com/?GlobalVariablesAreBad
- Are global variables bad? - https://stackoverflow.com/questions/484635/are-global-variables-bad
1.14.9 Writer Monad
The writer monad makes possible to compose functions which returns values and a log string.
The writer monad in no longer implemented in a simple way like in Haskell 98. It is now implemented as special case of the WriterT monad transformer.
New implementation of type constructor Writer:
>>> import Control.Monad.Writer >>> >>> :info Writer type Writer w = WriterT w Identity -- Defined in ‘Control.Monad.Trans.Writer.Lazy’ >>>
Old implementation of type constructor Writer: (Book: Learn You a Haskell)
newtype Writer w a = Writer { runWriter :: (a, w) } instance (Monoid w) => Monad (Writer w) where return x = Writer (x, mempty) (Writer (x,v)) >>= f = let (Writer (y, v')) = f x in Writer (y, v `mappend` v')
Documentation: Control.Monad.Writer
Example:
-- Haskell v7.10.2 -- >>> import Control.Monad.Writer >>> >>> :t writer writer :: MonadWriter w m => (a, w) -> m a >>> >>> :t runWriter runWriter :: Writer w a -> (a, w) >>> >>> :t execWriter execWriter :: Writer w a -> w >>> >>> :t tell tell :: MonadWriter w m => w -> m () >>> >>> writer (10, "The value is " ++ show 10) :: Writer String Int WriterT (Identity (10,"The value is 10")) >>> >>> let w = writer (10, "The value is " ++ show 10) :: Writer String Int >>> w WriterT (Identity (10,"The value is 10")) >>> >>> runWriter w (10,"The value is 10") >>> >>> execWriter w "The value is 10" >>> >>> :t tell tell :: MonadWriter w m => w -> m () >>> >>> :t writer writer :: MonadWriter w m => (a, w) -> m a :set +m :{ let fn1 :: Int -> Writer String Int fn1 x = writer (2 * x, "The value of x is : " ++ show x) :} >>> :t fn1 fn1 :: Int -> Writer String Int >>> >>> fn1 2 WriterT (Identity (4,"The value of x is : 2")) >>> >>> fn1 3 WriterT (Identity (6,"The value of x is : 3")) >>> >>> runWriter $ fn1 2 (4,"The value of x is : 2") >>> runWriter $ fn1 3 (6,"The value of x is : 3") >>> >>> fst . runWriter $ fn1 2 4 >>> fst . runWriter $ fn1 3 6 >>> >>> snd . runWriter $ fn1 2 "The value of x is : 2" >>> snd . runWriter $ fn1 3 "The value of x is : 3" >>> >>> execWriter $ fn1 3 "The value of x is : 3" >>> execWriter $ fn1 2 "The value of x is : 2" >>> >>> return 1 :: Writer String Integer WriterT (Identity (1,"")) >>> >>> return 100 :: Writer String Integer WriterT (Identity (100,"")) >>> >>> return (Just 100) :: Writer String (Maybe Integer) WriterT (Identity (Just 100,"")) >>> >>> runWriter (return 100 :: Writer String Integer) (100,"") >>> -- -- This version must be loaded from a file. -- fn2 :: Int -> Writer String Int fn2 x = do --writer (2 * x, "The value of x is : " ++ show x) tell ( "The value of x is : " ++ show x ) return ( 2 * x ) --- --- This version can be pasted in the repl --- :{ let fn2 :: Int -> Writer String Int fn2 x = do --writer (2 * x, "The value of x is : " ++ show x) tell ( "The value of x is : " ++ show x ) return ( 2 * x ) :} >>> :t fn2 fn2 :: Int -> Writer String Int >>> >>> fn2 2 WriterT (Identity (4,"The value of x is : 2")) >>> fn2 3 WriterT (Identity (6,"The value of x is : 3")) >>> {- Example from Learn You a Haskell - http://learnyouahaskell.com/for-a-few-monads-more logNumber :: Int -> Writer [String] Int logNumber x = Writer (x, ["Got number: " ++ show x]) -} :{ let logNumber :: Int -> Writer [String] Int logNumber x = writer (x, ["Got number: " ++ show x]) :} >>> :t logNumber logNumber :: Int -> Writer [String] Int >>> >>> logNumber 1 WriterT (Identity (1,["Got number: 1"])) >>> >>> logNumber 2 WriterT (Identity (2,["Got number: 2"])) >>> >>> runWriter $ logNumber 1 (1,["Got number: 1"]) >>> - multWithLog :: Writer [String] Int multWithLog = do a <- logNumber 3 b <- logNumber 5 return (a*b) :{ let multWithLog :: Writer [String] Int multWithLog = do a <- logNumber 3 b <- logNumber 5 return (a*b) :} >>> :t multWithLog multWithLog :: Writer [String] Int >>> >>> multWithLog WriterT (Identity (15,["Got number: 3","Got number: 5"])) >>> >>> runWriter multWithLog (15,["Got number: 3","Got number: 5"]) >>> >>> execWriter multWithLog ["Got number: 3","Got number: 5"] >>> multWithLog :: Writer [String] Int multWithLog = do a <- logNumber 3 b <- logNumber 5 tell ["Gonna multiply these two"] return (a*b) :{ let multWithLog :: Writer [String] Int multWithLog = do a <- logNumber 3 b <- logNumber 5 tell ["Gonna multiply these two"] return (a*b) :} >>> multWithLog WriterT (Identity (15,["Got number: 3","Got number: 5","Gonna multiply these two"])) >>> >>> runWriter multWithLog (15,["Got number: 3","Got number: 5","Gonna multiply these two"]) >>> :{ let multWithLog2 :: Writer [String] Int multWithLog2 = logNumber 3 >>= \a -> logNumber 5 >>= \b -> tell ["Gonna multiply these two"] >>= \_ -> return (a*b) :} >>> :t multWithLog2 multWithLog2 :: Writer [String] Int >>> >>> runWriter multWithLog2 (15,["Got number: 3","Got number: 5","Gonna multiply these two"]) >>> gcd' :: Int -> Int -> Writer [String] Int gcd' a b | b == 0 = do tell ["Finished with " ++ show a] return a | otherwise = do tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)] gcd' b (a `mod` b) :{ let gcd' :: Int -> Int -> Writer [String] Int gcd' a b | b == 0 = do tell ["Finished with " ++ show a] return a | otherwise = do tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)] gcd' b (a `mod` b) :} >>> :t gcd' gcd' :: Int -> Int -> Writer [String] Int >>> >>> gcd' 100 40 WriterT (Identity (20,["100 mod 40 = 20","40 mod 20 = 0","Finished with 20"])) >>> >>> runWriter $ gcd' 100 40 (20,["100 mod 40 = 20","40 mod 20 = 0","Finished with 20"]) >>> >>> import Control.Monad (mapM_) >>> >>> import Control.Monad (mapM_) >>> >>> mapM_ putStrLn $ snd $ runWriter $ gcd' 8 3 8 mod 3 = 2 3 mod 2 = 1 2 mod 1 = 0 Finished with 1 >>> >>> mapM_ putStrLn $ snd $ runWriter $ gcd' 100 68 100 mod 68 = 32 68 mod 32 = 4 32 mod 4 = 0 Finished with 4 >>> gcdReverse :: Int -> Int -> Writer [String] Int gcdReverse a b | b == 0 = do tell ["Finished with " ++ show a] return a | otherwise = do result <- gcdReverse b (a `mod` b) tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)] return result :{ let gcdReverse :: Int -> Int -> Writer [String] Int gcdReverse a b | b == 0 = do tell ["Finished with " ++ show a] return a | otherwise = do result <- gcdReverse b (a `mod` b) tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)] return result :} >>> :t gcdReverse gcdReverse :: Int -> Int -> Writer [String] Int >>> >>> mapM_ putStrLn $ snd . runWriter $ gcdReverse 39 106 Finished with 1 5 mod 1 = 0 6 mod 5 = 1 11 mod 6 = 5 28 mod 11 = 6 39 mod 28 = 11 106 mod 39 = 28 39 mod 106 = 39 >>>
1.14.10 See also
Monads
- Yet Another Monad Tutorial in 15 Minutes - Carpe diem (Felix's blog)
- Haskell Monad Tutorial - The Greenhorn's Guide to becoming a Monad Cowboy
- Monads for functional programming - Philip Wadler
- Haskell/Understanding monads - Wikibooks, open books for an open world
- Chapter 14. Monads - Real World Haskell
- Monads Demystified | tech guy in midtown
- In search of a Monad for system call abstractions - Taesoo Kim - MIT CSAIL
- All about Monads - Haskell Wiki
- CS 596 Functional Programming and Design Fall Semester, 2014 Doc 22 Monads & Design Patterns
List Monad
- learning Scalaz — List Monad
- Haskell/Understanding monads/List - Wikibooks, open books for an open world
- Haskell/Understanding monads/Maybe - Wikibooks, open books for an open world
Monads in Ocaml
Monads in F#
- The F# Computation Expression Zoo
- Computation Expressions (F#)
- F Sharp Programming/Computation Expressions
- The F# Computation Expression Zoo (PADL'14)
Option/ Maybe Monad
- One Div Zero: Why Scala's "Option" and Haskell's "Maybe" types will save you from null
- The Option Pattern/ Code Commit
- MayBe Monad: Usage Examples - CodeProject
- Sean Voisen » A Gentle Intro to Monads … Maybe?
- Niwi.Nz : A little overview of error handling.
- A Monad in Practicality: First-Class Failures - Quils in Space
- Option Monad in Scala | Patrick Oscar Boykin's Personal Weblog
IO Monad
2 Functional Languages
Note: There is no consensus about what really is a functional language. In this table were selected programming languages which can be programmed in functional-style or favors this style.
Some Functional programming languages:
Language | Evaluation | Typing | Type Inference | Pattern Matching | Syntax Sugars | GIL | TCO | OO | AGDT | Platform | Family | Currying | Feature |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Haskell | Lazy | Static | Yes | Yes | Yes | No | Yes | No | Yes | NAT | ML/SML | Yes | Concurrency, Parallelism and Purity |
Ocaml | Strict | Static | Yes | Yes | Yes | Yes | Yes | Yes | Yes | NAT/BC | ML/SML | Yes | |
F# (F sharp) | Strict | Static | Yes | Yes | Yes | No | Yes | Yes | Yes | .NET | ML/SML | Yes | .NET Integration |
Scheme | Strict | Dynamic | No | No | Yes/ Macros | * | Yes | No | No | - | Lisp | No | Minimalist Educational |
Clojure | Strict | Dynamic | No | Yes. Destructuring and macros | Yes/ Macros | No | No | No | No | JVM | Lisp | No | Java integration + Macros |
Scala | Strict | Static | Yes | Yes | Yes | No | Yes | Yes | Yes | JVM | Yes | Java integration + Type safety | |
Erlang | Strict | Dynamic | ? | Yes | Yes | No | Yes | ? | ? | VM/Bytecode | ? | Telecommunications, Servers, Concurrency | |
Elixir | Strict | Dynamic | ? | Yes | Yes | No | Yes | ? | ? | Erlang VM | - | ? | Erlang VM + macros |
Python | Strict | Dynamic | No | No | No | Yes | No | Yes | No | VM/Bytecode | - | No | Libraries and easier to use. |
JavaScript | Strict | Dynamic | No | No | No | ?* | No | Yes | No | VM/Interpreted | *Lisp/ Scheme | No | The only language allowed to run in the browser. |
R | Strict | Dynamic | No | No | No | ? | No | Yes | - | VM/Bytecode | *Lisp/ Scheme | No | DSL - Statistics |
Mathematica | Strict | Dynamic | Yes | ? | ? | ? | ?? | ? | ? | ? | No | DSL - Computer Algebraic System | |
Notes:
- AGDT - Algebraic Data Types
- GIL - Global Interpreter Locking. Languages with GIL cannot take advantage of multi-core processors.
- TCO - Tail Call Optimization. Languages without TCO cannot perform recursion safely. It can lead to a stack overflow for a big number of iterations.
- JVM - Java Virtual Machine / Java Platform
- .NET - Dot Net Platform: CLR - Virtual Machine
- NAT - Native Code. Native code is not portable like a virtual machine, its execution is constrained to the processor architecture and to the system calls of the operating system.
- VM - Virtual Machine
- OO - Object Orientated
- Currying - Curried functions like in Haskell, F# and Ocaml
- DSL - Domain Specific Language
- Syntax Sugars help increase expressiveness and to write shorter,
concise and more readable code.
- Short lambda functions:
- Haskell: (\ x y -> 3 * x + y)
- Ocaml and F# (fun x y -> x + y)
- Monad bind operator: >>= from Haskell
- Function application.
- The operator (|>) from F# that pipes an argument into a function. 10 |> sin |> exp |> cos is equivalent to: (sin (exp (cos 10)))
- Clojure (->) macro: (-> 10 Math/sin Math/exp Math/cos) which is expanded to: (Math/cos (Math/exp (Math/sin 10)))
- Function composition operator: (>>) from F# and (.) dot from Haskell
- Short lambda functions:
- JavaScript: Is single-thread with event loop and uses asynchronous IO (non blocking IO) with callbacks.
- It is controversial that Javascript is based on scheme. According to Douglas Crockford JavaScript is Scheme on a C clothe. With a C-like syntax {Reference}.
More Information: Comparison of Functional Programming Languages
3 Influential People
A selection of people who influenced functional programming:
- Alonzo Church, Mathematician -> Lambda Calculus
- Haskell Curry, Mathematician -> Concept of currying
- Robin Milner, Computer Scientist -> Type inference
- John McCarthy, Computer Scientist -> Creator of Lisp and the father of Artificial intelligence research.
- John Backus, Computer Scientist -> Backus-Naur form (BNF), Fortran Language,
- Philip Wadler, Theory behind functional programming and the use of monads in functional programming, the design of the purely functional language Haskell.
- Eugenio Moggi, Professor of computer science at the University of Genoa, Italy. - He first described the general use of monads to structure programs.
- Simon Peyton Jones, Computer Scientist -> Major contributor to the design of the Haskell programming language.
- John Hughes, Computer Scientist -> One of the most influentials papers in FP field: Why functional programing matters.
- Gerald Jay Sussman, Mathematician and Computer Scientist
- Scheme Lisp Language
- Book: Structure and Interpretation of Computer Programs
- Book: Structure and Interpretation of Classical Mechanics
- Lambda Papers: A series of MIT AI Memos published between 1975 and 1980, developing the Scheme programming language and a number of influential concepts in programming language design and implementation.
4 Miscellaneous
4.1 Selected Wikipedia Articles
General
- List of functional programming topics
- Comparison of Functional Programming Languages
- Functional programming
- Declarative programming
- Aspect-oriented programming
Functions
First Class Functions
- First-class function
- Pure function
- Side effect (computer science)
- Purely functional
- Referential transparency (computer science)
- Function type
- Arity
- Variadic function
Composition
- Function composition (computer science)
- Function composition - Mathematics
- Composability
- Functional decomposition
Scope
Currying and Partial Evaluation
Higher Order Functions, Closures, Anonymous Functions
- Anonymous function
- Closure (computer programming)
- Higher-order function
- Fixed-point combinator
- Defunctionalization
- Closure (computer programming))
- Callback (computer programming))
- Coroutine
Recursion
Lambda Calculus and Process Calculus
Evaluation
Related to Lazy Evaluation
Monads
Continuations
Fundamental Data Structures
Types
- Category theory
- Type Theory
- Type System
- Algebraic data type
- Type signature
- Enumerated type
- Product type
- Tagged union
- Dependent type
Concurrency
- Thread (computing)
- Concurrency (computer science)
- Concurrent computing
- Actor model
- Event loop
- Channel (programming)
- MapReduce
- Futures and promises
- Asynchronous I/O
- Multicore processor
Miscellaneous
- Call stack
- Call graph
- Reflection (computer programming)
- Function object
- Memoization
- Garbage collection (computer science)
Functional Languages
4.2 Selected Rosettacode Pages
4.2.1 Concepts Examples
4.2.2 Languages
4.3 Libraries and Frameworks
Python
- Useful Python libraries for functional programming:
Javascript
- Underscore.js: "Underscore is a JavaScript library that provides a whole mess of useful functional programming helpers without extending any built-in objects."
5 Reading
5.1 Monads
- Moggi E. Notions of computation and monads. Information and computation. 1991 Jul 1;93(1):55-92.
- Philip Wadler, How to declare an imperative, ACM Computing
Surveys, 29(3):240–263, September 1997. Available at
http://homepages.inf.ed.ac.uk/wadler/papers/monadsdeclare/monadsdeclare.ps
Note: Explains how IO monads works.
- Philip Wadler, The essence of functional programming. Invited talk, 19'th Symposium on Principles of Programming Languages, ACM Press, Albuquerque, January 1992. Available at http://homepages.inf.ed.ac.uk/wadler/papers/essence/essence.ps
- Philip Wadler, Monads for functional programming. Available at http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf
- Wadler, Philip. Comprehending monads. Mathematical structures in