* [[http://www.yinwang.org/blog-cn/2013/03/31/purely-functional|对函数式语言的误解]] * [[http://stackoverflow.com/questions/2835801/why-hasnt-functional-programming-taken-over-yet|Why hasn't functional programming taken over yet?]] * [[http://stackoverflow.com/questions/7875253/what-is-the-purpose-of-a-stack-why-do-we-need-it-msil|What is the purpose of a stack? Why do we need it? (MSIL)]] * [[http://www.ruanyifeng.com/blog/2017/02/fp-tutorial.html|函数式编程入门教程]] ====== Haskell ====== * [[https://github.com/fpinscala/fpinscala/wiki/A-brief-introduction-to-Haskell,-and-why-it-matters|A brief introduction to Haskell, and why it matters]] * [[http://learnyouahaskell.com/|Learn You a Haskell for Great Good!]] ====== Scheme ====== * [[http://www.yinwang.org/blog-cn/2012/08/01/interpreter|怎样写一个解释器]] * [[http://yinwang0.lofter.com/post/183ec2_47c086|怎样写一个解释器 (舊版)]] * [[http://mitpress.mit.edu/sicp/|Structure and Interpretation of Computer Programs]] * [[http://xuanji.appspot.com/isicp/|Structure and Interpretation of Computer Programs Interactive Version]] * [[wp>Scheme (programming language)|Scheme]] * [[http://racket-lang.org/|Racket]] ====== Scala ====== * [[http://www.artima.com/pins1ed/|Programming in Scala]] * [[http://www.artima.com/pins1ed/builtin-control-structures.html|Chapter 7 Built-in Control Structures]] * [[http://www.artima.com/pins1ed/for-expressions-revisited.html|Chapter 23 For Expressions Revisited]] * for 表達式 (和一般程式語言為 for 述句不同，for 表達式有返回值) 是 map、flatMap 和 filter 的語法糖，較容易讓人理解其意圖。 // definition、filter 和 yield 可選。yield 使得 for 表達式有返回值。 // 此例中，返回由 n 組成的列表 (list)。 for { p <- persons // a generator n = p.name // a definition if (n startsWith "To") // a filter } yield n * [[http://www.artima.com/pins1ed/working-with-lists.html|Chapter 16 Working with Lists]] * 所謂的高階函數 (higher-order function)，就是其輸入或返回的也是函數 (first-order function)。 * [[http://www.artima.com/pins1ed/working-with-lists.html#i364816247-1|16.7 Higher-order methods on class List]] * [[http://www.brunton-spall.co.uk/post/2011/12/02/map-map-and-flatmap-in-scala/|Map, Map and flatMap in Scala]] * flatMap: 先 Map，再 flat。Map(f) 對列表中每一個元素應用時，會得到列表 List[T]，最終得到 List[List[T]]。flat 把 List[List[T]] 中的每個一元素 List[T] 打散並加以合併，最終形成單一個列表 List[T]。 * [[http://daily-scala.blogspot.se/2010/05/zipwithindex.html|zipWithIndex]] * zipWithIndex: scala> val abcde = List('a', 'b', 'c', 'd', 'e') abcde: List[Char] = List(a, b, c, d, e) scala> abcde.zipWithIndex res15: List[(Char, Int)] = List((a,0), (b,1), (c,2), (d,3), (e,4)) * [[http://www.artima.com/pins1ed/type-parameterization.html|Chapter 19 Type Parameterization]] * 類型參數化 (即 C++ 的模板) * S <: T * S 是 T 的子類 (subclass)。 * S <: T 是否意味著 List[S] <: List[T]，是協變 (covariant，協同變動) 和逆協變所要解決的問題。預設為非協變 ( nonvariant)，即 List[S] 和 List[T] 之間不存在任何繼承關係。 * [[http://www.artima.com/pins1ed/implicit-conversions-and-parameters.html|Chapter 21 Implicit Conversions and Parameters]] * [[http://www.artima.com/pins1ed/implicit-conversions-and-parameters.html#21.5|21.5 Implicit parameters]] * [[http://daily-scala.blogspot.se/2010/04/implicit-parameters.html|Implicit Parameters]] * An implicit parameter is a parameter to method or constructor that is marked as implicit. This means that if a parameter value is not supplied then the compiler will search for an "implicit" value defined within scope (according to resolution rules.) Implicit parameter resolution rules will be discussed soon. * One important restriction is that there can only be a single implicit keyword per method. It must be at the start of a parameter list (which also makes all values of that parameter list be implicit). I further understand that only the last parameter list may be implicit. * [[https://www.artima.com/pins1ed/combinator-parsing.html|Chapter 31 Combinator Parsing]] * [[http://bitwalker.org/posts/2013-08-10-learn-by-example-scala-parser-combinators/|Learn by Example: Scala Parser Combinators]] * [[http://henkelmann.eu/2011/01/13/an_introduction_to_scala_parser_combinators|An Introduction To Scala Parser Combinators - Part 1: Parser Basics]] * [[http://henkelmann.eu/2011/01/28/an_introduction_to_scala_parser_combinators-part_2_literal_expressions|An Introduction To Scala Parser Combinators - Part 2: Parsing Literal Expressions]] * [[http://henkelmann.eu/2011/01/29/an_introduction_to_scala_parser_combinators-part_3_unit_tests|An Introduction To Scala Parser Combinators - Part 3: Writing unit tests for parsers]] * [[https://github.com/scala/scala-parser-combinators|Scala Standard Parser Combinator Library]] * Lexical 是特殊的 parser，取消 Inherited 中的 Tokens、Scanners 和 Parsers，可以看到 Lexical 自己定義的成員。 * 點擊 Type Members 中的 Parser，可以查看 Parser 提供的操作符 (如: ^^^)。 * 解析器 (parser) 組和子/連結符 (combinator): 解析器可以視作為一個函數，輸入為字串，輸出為一資料結構。透過組合子，Scala 可以將多個解析器合併成單一個解析器。 * Parser[T]: Input => ParseResult[T] * T: parse 之後的結果。 * Input: 可以是單純的字元串流 (type Elem = Char) 或是從 lexer 傳回的 (Reader[Elem])。 * ParseResult[T]: 可以是 Success(result: T, in: Input)，或是 Failure(errmsg: String, in: Input)。 * | combinator 會看到 call-by-name (a: => A) 的應用。 * | combinator 可以看做是函數，call-by-name 代表該參數只有在被調用到時才會執行。與其相對，一般我們看到參數傳遞的方式都是 call-by-value，即參數傳入函數之前，就會被求值 (執行)。 * [[http://www.scala-lang.org/index.html|The Scala Programming Language]] * [[https://www.jetbrains.com/idea/|IntelliJ IDEA]] * [[http://scala-ide.org/|Scala IDE for Eclipse]] * [[http://stackoverflow.com/questions/14796390/could-not-find-implicit-value-for-evidence-parameter-of-type-scala-reflect-class|Could not find implicit value for evidence parameter of type scala.reflect.ClassManifest[T]]] * 無法找到型別為 scala.reflect.ClassManifest[T] 的 implicit 參數，可以透過 import 引入正確的 implicit 參數解決。 * [[http://stackoverflow.com/questions/25222989/erasure-elimination-in-scala-non-variable-type-argument-is-unchecked-since-it|Erasure elimination in scala : non-variable type argument is unchecked since it is eliminated by erasure]] * 函式欲根據容器內的元素類型，調用對映的處理函式。 * 改由 caller 根據容器內的元素類型，傳給 callee 對映的處理函式 (callee(f)(xs: List[T]))。 ===== Functional Programming in Scala ===== * [[https://www.manning.com/books/functional-programming-in-scala|Functional Programming in Scala]] * Ch.1 * [[wp>Referential transparency]] * 程式中的表達式可以被其運算結果取代，不影響程式語義。 * Pure function * x 滿足 referential transparency，f(x) 亦滿足 referential transparency，則稱函式 f 為 pure。 * Ch.3 * [[wp>Algebraic data type]] * List 是一種代數資料型別，本身從其它 ADT 建構而成，也可以用來建構其它 ADT。 * Ch.4 * 例外不滿足 referential transparency。Option 和 Either 是較為推薦的錯誤處理方式。例外只有在程序無法合理進行下去才被丟出。 * Option 可以想成是最多只有包含一個元素的 List，None 對應 Nil。 * 一般函式透過 lifting 可以處理 Option。 // (x: Option[A]) => x map f 可以寫成 _ map f def lift[A, B](f: A => B): Option[A] => Option[B] = (x: Option[A]) => x map f val absO: Option[Double] => Option[Double] = lift(math.abs) // 注意! 用 map/flatMap 實現不容易閱讀。把 Option 當作 List，用 for-comprehension 實現。 def map2[A, B, C](a: Option[A], b: Option[B])(f: (A, B) => C): Option[C] = for { aa <- a bb <- b } yield f(aa, bb) * [[http://softwareengineering.stackexchange.com/questions/255696/what-is-a-lifted-representation|What is a “lifted representation”?]] * xs map f，f 返回 Option。我們希望若 xs 任一元素 apply f 返回 None，則 xs map f 返回 None。 def traverse[A, B](a: List[A])(f: A => Option[B]): Option[List[B]] = a match { case Nil => Some(Nil) case h::t => map2(f(h), traverse(t)(f))(_ :: _) } * [[http://stackoverflow.com/questions/26602611/how-to-understand-traverse-traverseu-and-traversem|How to understand traverse, traverseU and traverseM]] * Either 比 Option 對錯誤可以帶有更多資訊，而不只是返回 None。Right 代表正確，Left 代表錯誤。 * 我們可以將 side-effect 包裝成一般 value 返回加以處理。Monad 就是此種概念下的產物。 * Ch.5 * [[https://github.com/fpinscala/fpinscala/wiki/Chapter-5:-Strictness-and-laziness|Chapter 5: Strictness and laziness]] * 一個函式稱為 strict，代表在被調用之前，其參數均被求值 (所有參數均為 call-by-value)。我們在一般編程語言中所見到的函式皆為 strict。 * 一個函式若有 call-by-name 參數，即為 non-strict (not strict)。 // cond - call by value // onTrue, onFalse - call by name def if2[A](cond: Boolean, onTrue: => A, onFalse: => A): A = if (cond) onTrue else onFalse // onTrue 和 onFalse 在傳入 if2 時不會被求值，此時才會根據 cond 決定誰被求值。 def if2[A](cond: Boolean, onTrue: () => A, onFalse: () => A): A = if (cond) onTrue() else onFalse() // 上面代碼是此版本的語法糖。onTrue 和 onFalse 分別是 lamda function。 * [[http://stackoverflow.com/questions/13337338/call-by-name-vs-call-by-value-in-scala-clarification-needed|Call by name vs call by value in Scala, clarification needed]] * [[http://alvinalexander.com/source-code/scala/simple-scala-call-name-example|A simple Scala call-by-name example]] * 未被求值的表達式 (onTrue() 和 onFalse()) 又被稱為 [[wp>Thunk]]。 * call-by-name 的參數如果有副作用，必須要注意該副作用可能會執行多次。 def maybeTwice(b: Boolean, i: => Int) = if (b) i + i else 0 // i 被引用兩次，由於 i 是 call-by-name，代表 i 會被求值兩次。 val x = maybeTwice(true, { println("hi"); 1 + 41 }) // 印出兩次 "hi"，x = 84。 def maybeTwice(b: Boolean, i: => Int) = { lazy val j = i // j 第一次被引用，會對 i 求值，並將該值 cache 起來; 後續引用 j 不再對 i 求值。 if (b) j + j else 0 // i 被引用兩次，由於 i 是 call-by-name，代表 i 會被求值兩次。 val x = maybeTwice(true, { println("hi"); 1 + 41 }) // 印出一次 "hi"，x = 84。 * [[http://alvinalexander.com/scala/how-to-use-stream-class-lazy-list-scala-cookbook|How to use the Scala Stream class, a lazy version of List]] * Stream 類似 List。差別在於對其做 map 或是其它運算時，Stream 只會在 caller 需要時，對其中元素進行運算; 而 List 是對其中所有元素一次進行運算。 scala> (1 to 5).toList res10: List[Int] = List(1, 2, 3, 4, 5) // list 中所有元素立刻被求值。 scala> (1 to 5).toStream res11: scala.collection.immutable.Stream[Int] = Stream(1, ?) // ? 代表剩下部分未被求值。 * [[wp>Separation of concerns]]。將代碼視作為資料在程序中傳遞，在適當時候可以調用。匿名函式或是 Option 都是此種概念的應用。[[wp>Lazy evaluation]] 讓我們可以將表達式的描述和求值加以分開，只有在需要時才對表達式求值。 * [[http://weblog.raganwald.com/2007/03/why-why-functional-programming-matters.html|Why Why Functional Programming Matters Matters]] * Ch.6 * 為保持 referential transparency，把 side effect 或是 state 作為返回值。 ===== Scalaz ===== * [[https://github.com/scalaz/scalaz|Scalaz]] * [[http://stackoverflow.com/questions/4863671/good-scalaz-introduction/12391259|Good scalaz introduction]] * [[http://eed3si9n.com/learning-scalaz/|learning Scalaz]] * [[https://hseeberger.wordpress.com/2010/11/25/introduction-to-category-theory-in-scala/|Introduction to Category Theory in Scala]] * [[http://stackoverflow.com/questions/16526282/use-scalaz-in-console-repl-without-creating-a-project|Use scalaz in console repl without creating a project]] * $ sbt set scalaVersion := "2.12.1" set libraryDependencies += "org.scalaz" %% "scalaz-core" % "7.2.9" set initialCommands += "import scalaz._, Scalaz._" session save console * # 下載 scalaz-core_2.12-7.2.9.jar $ scala -cp scalaz-core_2.12-7.2.9.jar ===== ScalaTest ===== * [[http://www.scalatest.org/|ScalaTest]] * [[http://www.scalatest.org/quick_start|ScalaTest quick start]] ====== 術語 ====== * [[wp>Lambda calculus]] * [[wp>S-expression]] * [[wp>Closure (computer programming)|Closure]] * [[wp>Monad (functional programming)|Monad]] * [[http://yinwang0.lofter.com/post/183ec2_b1afb9|为什么说面向对象编程和函数式编程都有问题]] * [[https://www.youtube.com/watch?v=ZhuHCtR3xq8|Brian Beckman: Don't fear the Monad]] * [[http://mdjnewman.me/2013/10/dont-fear-the-monad/|Don't fear the Monad]] * [[http://www.zohaib.me/yet-another-what-is-a-monad-post/|Yet another "What is a Monad" post]] * [[http://mvanier.livejournal.com/3917.html|Yet Another Monad Tutorial (part 1: basics)]] * [[http://www.idryman.org/blog/2014/01/23/yet-another-monad-tutorial/|Yet Another Monad Tutorial in 15 Minutes]] * [[http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf|Monads for functional programming]] * [[http://www.jianshu.com/p/31377066bf97|Scala和范畴论 -- 对Monad的一点认识]] * [[http://zhuoqiang.me/what-is-monad.html|Monad 最简介绍]] * [[https://blog.codecentric.de/en/2015/12/monads-demystified/|Monads demystified]] * [[http://stackoverflow.com/questions/2704652/monad-in-plain-english-for-the-oop-programmer-with-no-fp-background/2704795#2704795|Monad in plain English? (For the OOP programmer with no FP background)]] * [[http://james-iry.blogspot.se/2007/09/monads-are-elephants-part-1.html|Monads are Elephants Part 1]] * [[http://www.jianshu.com/p/9ff3040c7159|Monads are Elephants(4) 翻譯]] * [[https://darrenjw.wordpress.com/2016/04/15/first-steps-with-monads-in-scala/|First steps with monads in Scala]] * [[https://www.youtube.com/watch?v=QqEeBoZ8qxA|Scala Monads Declutter Your Code With Monadic Design]] ====== 外部連結 ====== * [[http://www.haskell.org/haskellwiki/Haskell|The Haskell Programming Language]] * [[http://patternsinfp.wordpress.com/|Patterns in Functional Programming]] * [[http://blog.johantibell.com/2010/09/slides-from-my-high-performance-haskell.html|High-Performance Haskell]] * [[http://www.well-typed.com/blog/70|The New Cloud Haskell]] * [[http://blog.codacy.com/2015/07/03/how-to-learn-scala|How to learn Scala]] * [[http://danielwestheide.com/scala/neophytes.html|The Neophyte's Guide to Scala]] * [[http://pointlessfunctor.blogspot.tw/|Pointless Functors]]