[Lecture Notes]Functional Programming,University of Mississippi

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

CSci 555: Functional Programming
Spring Semester 2016
Lecture Notes

本帖隐藏的内容

Sections

• Schedule, Lecture Notes, and Examples
• Reference Materials and Other Resources
• 
  

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏1 回帖

关键词：Programming University Functional Universit function University

1. Feb 10 08:27 2016 sqrt.scala Page 1
   
2. 
   
3. 
   
4. /* Square Root by Newton's Method -- Version 1
   
5.    Functional Programming Example
   
6.    H. Conrad Cunningham, Professor, Computer and Information Science
   
7.    University of Mississippi
   
8. 
   
9.    Developed for CSci 555, Functional Programming, Spring 2016
   
10. 
    
11. 1234567890123456789012345678901234567890123456789012345678901234567890
    
12. 
    
13. 2016-02-10: Developed from 2015 Elixir version
    
14. 
    
15. Function sqrt computes the square root of its argument x using
    
16. Newton's method.  
    
17. 
    
18. I adapted this square root module from an Elixir version, which was,
    
19. in turn, adapted from a Lua version, which was, in turn, adapted from
    
20. the Scheme code in section 1.1.7 of Abelson and Sussman's Structure
    
21. and Interpretation of Computer Programs (SICP) textbook. I changed the
    
22. function names to better match the Scala naming convention.
    
23. 
    
24. I have only tested this code minimally.
    
25. 
    
26. Scala and functional programming highlights:
    
27. - Uses object to define a module
    
28. - Uses type inference as much as possible (But I suggest it is
    
29.   better to give return types for public functions.)
    
30. - Requires return type for sqrtIter because it is recursive
    
31. - Makes all functions visible.  Should hide all but sqrt.
    
32. - Uses tail recursion
    
33. - Calls Math.abs.
    
34. 
    
35. */
    
36. 
    
37. object Sqrt {
    
38. 
    
39.   def sqrt(x: Double) = sqrtIter(1.0, x)
    
40. 
    
41.   // Tail recursive auxiliary function
    
42.   def sqrtIter(guess: Double, x: Double) : Double =
    
43.     if (isGoodEnough(guess,x))
    
44.       guess
    
45.     else
    
46.       sqrtIter(improve(guess,x),x)
    
47. 
    
48.   def isGoodEnough(guess: Double, x: Double) =
    
49.     Math.abs(square(guess)- x)< 0.001
    
50. 
    
51.   def square(x: Double) = x * x
    
52. 
    
53.   def improve(guess: Double, x: Double) = average(guess,x/guess)
    
54. 
    
55.   def average(x: Double, y: Double) = (x + y) / 2
    
56. 
    
57. 
    
58. 
    
59. 
    
60. 
    
61. 
    
62. 
    
63. 
    
64. Feb 10 08:27 2016 sqrt.scala Page 2
    
65. 
    
66. 
    
67.   // Should implement extensive tesing externally
    
68.   def main(args: Array[String]) {
    
69.     println("square root of 9 is " + sqrt(9.0))
    
70.   }
    
71. 
    
72. }

复制代码

1. /* Summation Function with Functional Parameters
   
2.    Functional Programming Example - Higher Order
   
3.    H. Conrad Cunningham, Professor
   
4.    Computer and Information Science
   
5.    University of Mississippi
   
6. 
   
7.    Developed for CSci 555, Functional Programming, Spring 2016
   
8. 
   
9. 1234567890123456789012345678901234567890123456789012345678901234567890
   
10. 
    
11. 2016-02-10: Developed from 2015 Elixir version
    
12. 
    
13. I adapted this summation module from an Elixir version, which as, in
    
14. turn, adapted from a Lua version, which was, in turn, adapted from the
    
15. Scheme code in section 1.2.1 of Abelson and Sussman's Structure and
    
16. Interpretation of Computer Programs (SICP).
    
17. 
    
18. I have only tested this minimally.
    
19. 
    
20. Scala and functional programming highlights:
    
21. - Illustrates generalization of first-order functions into
    
22.   higher-order
    
23. - Explicitly defined return type as Double
    
24. - Uses anonymous functions
    
25. - Defines val to have function value
    
26. 
    
27. */
    
28. 
    
29. object Summation {
    
30. 
    
31.   /* Function "sumIntegers" computes the sum of the integers in the
    
32.      range from "a" through "b".
    
33.   */
    
34. 
    
35.   def sumIntegers(a: Int, b: Int): Int =
    
36.     if (a > b)
    
37.       0
    
38.     else
    
39.       a + sumIntegers(a+1,b)
    
40. 
    
41.   /* Function "sumCubes" computes the sum of the cubes of the
    
42.      integers in the range from "a" through "b".
    
43.   */
    
44. 
    
45.   def sumCubes(a: Int, b: Int): Double = {
    
46.     val cube = ((x: Int) => x * x * x)
    
47.     if (a > b)
    
48.       0
    
49.     else
    
50.       cube(a) + sumCubes(a+1,b)
    
51.   }
    
52.   
    
53.   /* Function "piSum" computes the sum of the series of terms
    
54.      1/(i*(i+2)) from i = a until i > b.
    
55.    
    
56.      For a = 1 and b = 10 this would be 1/1*3 + 1/5*7 + 1/9*11.
    
57.      For initial a = 1, this converges slowly on PI/8.
    
58.   */
    
59. 
    
60.   def piSum(a: Int, b: Int): Double =
    
61.     if (a > b)
    
62.       0.0
    
63.     else
    
64.       1.0 / (a * (a+2)) + piSum(a+4,b)
    
65. 
    
66. 
    
67.   /* The above all satisfy the following template of the following
    
68.      form for some NAME, TERM, and NEXT.
    
69. 
    
70.        def NAME(a: Int, b: Int): Double =
    
71.          if (a < b) 0 else TERM(a) + NAME(NEXT(a),b)
    
72. 
    
73.     We can express this function as a higher-order function (for NAME)
    
74.     with functional arguments for the operations TERM and NEXT.
    
75. 
    
76.     Function "sum" adds the values of the application of function
    
77.     "term" to integer i for all integers i in the range [1,b], where
    
78.     the difference from i to its successor j is next(i).
    
79. 
    
80.     Note: I explicitly defined the return type to be Double to avoid
    
81.     complicating the function with generics and extra parameters.
    
82. 
    
83.   */
    
84.   
    
85.   def sum(term: Int => Double, a: Int, next: Int => Int, b: Int): Double=
    
86.     if (a > b)
    
87.       0.0
    
88.     else
    
89.       term(a) + sum(term,next(a),next,b)
    
90.       
    
91.   // sumIntegers in terms of sum
    
92.   def sumIntegers2(a: Int, b: Int) =
    
93.     sum(((x:Int) => x), a: Int, ((x:Int) => x+1), b:Int)
    
94. 
    
95.   // sumCubes in terms of sum
    
96.   def sumCubes2(a: Int, b: Int): Double = {
    
97.     def cube(x: Int): Double = x * x * x
    
98.     def incr(x: Int): Int    = x+1
    
99.     sum(cube,a,incr,b)
    
100.   }
     
101. 
     
102.   // piSum in terms of sum
     
103.   def piSum2(a: Int, b: Int): Double = {
     
104.     val piTerm = ((x: Int) => 1.0 / (x * (x+2)))
     
105.     def piNext(x: Int): Int    = x + 4
     
106.     sum(piTerm,a,piNext,b)
     
107.   }
     
108. 
     
109.   /* Function "sum" can be further generalized in various ways.
     
110. 
     
111.      Question: How would we need to modify "sum" so that the resulting
     
112.      higher-order function is capable of either summing or multiplying
     
113.      the integers over a range?
     
114.   */
     
115. 
     
116.   // Should implement extensive tesing externally
     
117.   def main(args: Array[String]) {
     
118.     println("sumIntegers(1,10)  = " + sumIntegers(1,10))
     
119.     println("sumIntegers2(1,10) = " + sumIntegers2(1,10))
     
120.     println("sumCubes(1,5)      = " + sumCubes(1,5))
     
121.     println("sumCubes2(1,5)     = " + sumCubes2(1,5))
     
122.     println("piSum(1,10)        = " + piSum(1,10))
     
123.     println("piSum2(1,10)       = " + piSum2(1,10))
     
124.   }
     
125. 
     
126. }

复制代码

1. /* Functional Programming Example -- Greatest Common Divisor
   
2.    H. Conrad Cunningham, Professor
   
3.    Computer and Information Science
   
4.    University of Mississippi
   
5. 
   
6.    Developed for CSci 555, Functional Programming, Spring 2016
   
7. 
   
8. 1234567890123456789012345678901234567890123456789012345678901234567890
   
9. 
   
10. 2016-02-10: Developed from 2015 Elixir version
    
11. 
    
12. I adapted this greatest common divisor (gcd) module from an Elixir
    
13. version, which as, in turn, adapted from a Lua version, which was, in
    
14. turn, adapted from the Scheme code in section 1.2.1 of Abelson and
    
15. Sussman's Structure and Interpretation of Computer Programs (SICP).
    
16. 
    
17. I have only tested this minimally.
    
18. 
    
19. Scala and functional programming highlights:
    
20. - States complexity measures
    
21. 
    
22. */
    
23. 
    
24. object GCD {
    
25. 
    
26.   /* Function "gcd" computes the greatest common divisor of its two
    
27.      nonegative number arguments using Euclid's algorithm.  It is
    
28.      based on property: If r is the remainder of a divided by b, then
    
29.      the common divisors of a and b are precisely the same as the
    
30.      common divisors of b and r.
    
31.   
    
32.      Time complexity:  O(log max(a,b))
    
33.      Space complexity: O(1) with tail call optimization
    
34.   */
    
35. 
    
36.   def gcd(a: Int, b: Int): Int = b match {
    
37.     case 0 => a
    
38.     case n => gcd(b, a % b)   // tail recursion
    
39.   }
    
40. 
    
41.   // Should implement extensive tesing externally
    
42.   def main(args: Array[String]) {
    
43.     println("gcd(20,15) is " + gcd(20,15))
    
44.     println("gcd(15,20) is " + gcd(15,20))
    
45.     println("gcd(39,42) is " + gcd(39,42))
    
46.     println("gcd(13,19) is " + gcd(13,19))
    
47.   }
    
48. 
    
49. }

复制代码

1. /* Derivative Function with Function Return
   
2.    Functional Programming Example -- Higher Order
   
3.    H. Conrad Cunningham, Professor
   
4.    Computer and Information Science
   
5.    University of Mississippi
   
6. 
   
7.    Developed for CSci 555, Functional Programming, Spring 2016
   
8. 
   
9. 1234567890123456789012345678901234567890123456789012345678901234567890
   
10. 
    
11. 2016-02-10: Developed from 2015 Elixir version
    
12. 
    
13. I adapted this derivative module from an Elixir version, which was, in
    
14. turn, adapted from a Lua version, which was, in turn, adapted from the
    
15. Scheme code in section 1.2.1 of Abelson and Sussman's Structure and
    
16. Interpretation of Computer Programs (SICP).
    
17. 
    
18. I have only tested this minimally.
    
19. 
    
20. Scala and functional programming highlights:
    
21. - Takes a function argument
    
22. - Returns a function
    
23. - Uses anonymous function
    
24. 
    
25. */
    
26. 
    
27. object Derivative {
    
28. 
    
29.   /* Function "deriv" takes a single-argument function "f" and a small
    
30.      delta "dx" and returns a single-argument function (closure) that
    
31.      computes an approximation of the value of the derivative at the
    
32.      value of its argument.
    
33. 
    
34.      Definition of derivative: lim(dx->0) (f(x+dx) - f(x)) / dx
    
35.    */
    
36. 
    
37.   def deriv(f: Double => Double, dx: Double): Double => Double =
    
38.     ((x: Double) => (f(x+dx) - f(x)) / dx)
    
39. 
    
40.   // Should implement extensive tesing externally
    
41.   def main(args: Array[String]) {
    
42.     def cube(x: Double) = x * x * x
    
43.     val dx              = 0.001
    
44.     val derivCube       = deriv(cube,dx)
    
45.     def actualDerivCube(x: Double) = 3 * x * x
    
46. 
    
47.     println("deriv(cube,dx)(3.0)  = " + deriv(cube,dx)(3.0))
    
48.     println("actualDerivCube(3.0) = " + actualDerivCube(3.0))
    
49.   }
    
50. 
    
51. }

复制代码

1. # Functional Programming Example -- Factorial
   
2. # H. Conrad Cunningham, Professor
   
3. # Computer and Information Science
   
4. # University of Mississippi
   
5. 
   
6. # Developed for CSci 556, Multiparadigm Programming, Spring 2015
   
7. 
   
8. # 34567890123456789012345678901234567890123456789012345678901234567890
   
9. 
   
10. # 2015-02-07: Developed from 2013 Lua version
    
11. 
    
12. # This factorial module is adapted from a Lua version, which itself
    
13. # is adapted from the Scheme code in section 1.2.1 of Abelson and
    
14. # Sussman's Structure and Interpretation of Computer Programs (SICP)
    
15. 
    
16. defmodule Factorial do
    
17.   
    
18.   # Function "factorial" computes the factorial for nonnegative number
    
19.   # "n" using backward linear recursion. That is, the single recursive
    
20.   # call needed for each level is embedded in a larger expression
    
21.   # whose computation must be completed upon return from the recursive
    
22.   # call.
    
23.   
    
24.   # Time complexity:  O(n) recursive calls of factorial
    
25.   # Space complexity: O(n) active calls each taking a frame
    
26. 
    
27.   def factorial(0)            do 1 end
    
28.   def factorial(n) when n > 0 do n * factorial(n-1) end
    
29. 
    
30.   # Function "factorial2" computes the factorial for nonnegative
    
31.   # number "n" using a tail recursive auxiliary function with an
    
32.   # accumulating parameter.  Tail recursion is forward linear
    
33.   # recursion. Auxiliary function "fact_iter" is nested inside
    
34.   # "factorial2" and can only be called from "factorial2".
    
35.   
    
36.   # Time complexity:  O(n) recursive calls of fact_iter
    
37.   # Space complexity: O(1) with tail call optimization
    
38. 
    
39.   def factorial2(n) when is_integer(n) and n >= 0 do
    
40.     fact_iter(n,1)
    
41.   end
    
42. 
    
43.   # private tail recursive auxiliary function with accumulating
    
44.   # parameter (accumulator)
    
45.   
    
46.   defp fact_iter(0,r) do r end
    
47.   defp fact_iter(n,r) do fact_iter(n-1,n*r) end
    
48. 
    
49. end

复制代码

1. # Functional Programming Example -- Fibonacci
   
2. # H. Conrad Cunningham, Professor
   
3. # Computer and Information Science
   
4. # University of Mississippi
   
5. 
   
6. # Developed for CSci 556, Multiparadigm Programming, Spring 2015
   
7. 
   
8. # 34567890123456789012345678901234567890123456789012345678901234567890
   
9. 
   
10. # 2015-02-08: Developed from 2013 Lua version
    
11. 
    
12. # The functions in this Fibonacci number module are adapted from Lua
    
13. # versions, which themselves are adapted from the Scheme code in
    
14. # section 1.2.4 of Abelson and Sussman's Structure and Interpretation
    
15. # of Computer Programs (SICP) textbook.
    
16. 
    
17. defmodule Fibonacci do
    
18. 
    
19.   def fib(0) do 0 end
    
20.   def fib(1) do 1 end
    
21.   def fib(n) when is_integer(n) and n >= 2 do
    
22.     fib(n-1) + fib(n-2) # double (tree) recursion
    
23.   end
    
24. 
    
25.   # Function "fib2" takes nonnegative number "n" and computes the nth
    
26.   # (second order) Fibonacci number.  It uses "fib_iter" a tail
    
27.   # recursive auxiliary function with two accumulating parameters.
    
28.   
    
29.   # Time complexity:   O(n) recursive calls
    
30.   # Space complextity: O(n); O(1) with tail call optimization
    
31. 
    
32.   def fib2(n) when is_integer(n) and n >= 0 do fib_iter(1,0,n) end
    
33. 
    
34.   # Tail recursive function using accumulating parameters a and b
    
35.   defp fib_iter(_,b,0) do b end
    
36.   defp fib_iter(a,b,m) do fib_iter(a+b,a,m-1) end
    
37. 
    
38. end

复制代码

1. # Functional Programming Example #  Exponentiation
   
2. # H. Conrad Cunningham, Professor
   
3. # Computer and Information Science
   
4. # University of Mississippi
   
5. 
   
6. # Developed for CSci 556, Multiparadigm Programming, Spring 2015
   
7. 
   
8. # 34567890123456789012345678901234567890123456789012345678901234567890
   
9. 
   
10. # 2015-02-07: Developed from 2013 Lua version
    
11. 
    
12. # This exponentiation module is adapted from a Lua version, which
    
13. # itself is adapted from the Scheme code in section 1.2.4 of Abelson
    
14. # and Sussman's Structure and Interpretation of Computer Programs
    
15. # (SICP)
    
16. 
    
17. defmodule Expt do
    
18. 
    
19.   # Function "expt1" computes b^n (b raised to power n) using backward
    
20.   # linear recursion.
    
21. 
    
22.   # Time complexity:  O(n) recursive calls
    
23.   # Space complexity: O(n) active recursive calls
    
24. 
    
25.   def expt1(b,n) when is_number(b) and is_integer(n) and n >= 0 do
    
26.     _expt1(b,n)
    
27.   end
    
28.   
    
29.   # private auxiliary to avoid repeated type checks
    
30.   defp _expt1(_,0) do 1 end
    
31.   defp _expt1(b,n) do b * _expt1(b,n-1) end
    
32. 
    
33. 
    
34.   # Function "expt2" computes b^n using tail recursion.
    
35. 
    
36.   # Time complexity:  O(n) recursive calls
    
37.   # Space complexity: O(1) with tail call optimization
    
38. 
    
39.   def expt2(b,n) when is_number(b) and is_integer(n) and n >= 0 do
    
40.     _expt2(b,n,1)
    
41.   end
    
42. 
    
43.   # private tail recursive auxiliary (called expt_inter in SICP)
    
44.   defp _expt2(_,0,p) do p end
    
45.   defp _expt2(b,n,p) do _expt2(b,n-1,b*p) end
    
46. 
    
47. 
    
48.   # Fuction "expt3" computes b^n using a logarithmic algorithm and
    
49.   # backward recursion.  It takes advantage of squaring.
    
50.   #
    
51.   #   b^n = (b^(n/2)) * (b^(n/2)) if n even
    
52.   #   b^n = b * b^(n-1)           if n odd
    
53. 
    
54.   # Time complexity:  O(log n) recursive calls
    
55.   # Space complexity: O(log n) active recursive calls needing
    
56.         #                   stack frames
    
57. 
    
58.   def expt3(b,n) when is_number(b) and is_integer(n) and n >= 0 do
    
59.      _expt3(b,n)
    
60.   end
    
61. 
    
62.   defp _expt3(_,0) do 1 end
    
63. 
    
64.   defp _expt3(b,n) do
    
65.     if rem(n,2) == 0  do  #  i.e. even
    
66.       exp = _expt3(b,div(n,2))
    
67.       exp * exp           #  backward recursion
    
68.     else                  # i.e. odd
    
69.       b * _expt3(b,n-1)   #  backward recursion
    
70.     end
    
71.   end
    
72. 
    
73. end

复制代码

多谢楼主

顶顶DING