请不要吐槽标题，因为不知道叫啥就从手边的地狱训练摇滚贝斯上随便选一个名字
说起函数式编程大部分人的第一感觉好像很厉害的样子。不过其实函数式编程由于其历史悠久在计算机发展比较早的欧美其实是非常普遍的。我在的这个十八线学校甚至把这门课放到了大一来上， 国内由于大多数的程序员都是从c系语言开始接触计算机编程的所以不习惯才觉得艰涩吧。我校使用Haskell来教授这门课而没有采用更加友好的Lisp家族，主要原因可能是出于更加学术的考虑，毕竟Haskell中的很多理念都核能体现纯函数式编程。不过话说回来，函数式编程有着和面向对象差不多容量的知识和内容，我在这一学期学到的知识也只是相当于大一上完C语言程序设计的水平吧（笑），所以这里会有很多我理解不对的地方，希望自己慢慢的来改吧。
下面是正文：
函数式编程的第一步是 忘掉你学过的所有C系列语言的语法和编程思想，忘掉变量，忘掉流程控制。
在C系类的语言中，我们以描述逻辑变化的方式（控制语句）来描述问题，以变化数据的抽象（变量，对象）来描述客观世界中的物体。但是在函数式编程中我们的目标有所变化，我们更加关注与如何描述一个数学表达式。
思考如何描述以下情形：
幼儿园小朋友排队，一共有4个小朋友，请问有几种不同的排法，请罗列？
学过初中数学显然可以知道有n!种不同的排法我们只需要把这些不同的排法打印出来就可以了。为了解答这道题目我们首先需要设一下，这些小朋友的名字是AA,BB,CC,DD(我懒，凑活着吧)，在Haskell当中我们可以用下面的语句来描述这个操作
data Child = AA | BB | CC | DD
data关键字可以让我们很轻松的完成定义某种类型（小朋友）这个操作，在haskell中类型被称为type，而构成type的不同值构造子（换句话说定义的方法）写在等号右侧并且使用“ | ” 隔开，“ | ”被称为guard, 它完成了不同定义方法的分割，在后面我们将看到它的作用。
有了假设，我们终于可以来正面描述这个问题了，先用数学语言，已知集合children中有四个元素AA,BB,CC,DD，这四个元素的全排列构一个新集合，求这个新集合。
ok,先描述集合children：
let children = [AA, BB, CC, DD]
在haskell中当我们需要设一个自变量（不是变量）的时候我们可以使用let关键字. " [] "在haskell中表示了一个list。
你忘记c语言了吗？这里的let 根本不是在定义一个变量，因为在haskell里根本没有变量这种东西，这一切真的是字面意思定义了一个表达式, let a= 1 a=a+1 是不会让你得到你想要的东西的！！！！！也请不要回想任何关于其他普通语言list或者是数组的定义！！！
接下来表述问题的已知条件，所求
permutation :: [Child] -> [[Child]]
haskell中我们可以使用函数来描述一个问题（过程，算法），函数permutation 表达了算法对于某一个给定的Child list（小朋友们），可以得到Child list 的list(小朋友们的不同组合).当然函数也是有类型的，它的类型可以用“->” 来表示啦。
思考，对于确定的集合是否有唯一确定的全排列？在这里显然是成立的（不证明），那么集合和全排列之间可以描述为一种映射关系，在函数式编程中，我们使用函数来描述这种对于确定输入存在确定输出的映射关系。在常规编程中我们对于函数的定义显然没有那么严格，例如写一个函数来返回某一个文件中的字符串，只要文件在变化，那么函数的返回值必然就是有变化的，输入和输出不需要存在确定的关系。这种函数被称为不纯函数，或者叫有副作用的函数。函数式编程只允许纯函数，对于IO操作需要使用别的工具（Monad）, 所以暂时写不了hello world。
回想一下求全排列的算法，首先假设n-1个元素已经被全排列，接着把第n号元素插入已经排好的各个不同的全排列中，接着递归完成，这是递归版本分治算法的常见思路。
似乎有点麻烦， 我们先来计算一下有多少种可能吧！由全排列公式我们很容易得到可能性应该是4！，ok试着使用haskell函数计算一下4！吧,递归得到！
factorial :: Int -> Int ---- haskell 中Integer的类型是Int,具体的就直接hoogle吧！
factorial 1 = 1
factorial n = n * (factorial n-1)
ghci> factorial 4
24
在递归中，我们需要声明边界条件和对于f(n)的情况, 看看haskell代码，很好完全一致！编译器会用模式匹配的方式去匹配我们的输入如果是1就会输出1， n 就会递归向下直到1位置(可以在ghci交互式命令行中验证)
=。=，这里显然漏了一些情况 对于n <= 0的情况我们没有讨论，我们总不能去模式匹配小于零的所有情况吧！这时候我们需要guard来重写我们的函数，guard分割了我们函数在不同条件下的不同输出，效果很像if-else, 虽说如此还是希望忘记能c, TvT。另外Haskell中函数的定义其实是可以不写的，毕竟是高级语言嘛，类型推导必须有。
factorial n
| n <= 1 = 1 -- 我很懒，其实应该抛出异常
| otherwise = n * (factorial n-1)
有点意思，试试我们的小朋友类型
val :: Child -> Int
val AA = 1
val BB = 2
val CC = 3
-----------------------------
ghci> val A
1
nice! 不过在继续之前的问题，关于list还是有必要先熟悉一下的，毕竟之前说了这里的list和数组之类的完全不是一种东西。虽然很烦但是还是要说忘掉迭代那些c语言里的list操作，全部没用。
head [1,2,3]
1
tail [1,2,3]
3
[1,2,3] ++ [4]
[1,2,3,4,5]
concat [[1,2],[3,4]]
[1,2,3,4]
啊似乎没有什么不一样的,然而
1:[2,3,4]
[1,2,3,4]
- 求和
sum [] = []
sum (x:xs) = x + (sum xs)
什么list居然可以被模式匹配。仔细想了想，好像终于明白了什么，haskell里的list的定义应该是这样子的
data List a = [] | a `:` (List a)
没错，list是使用递归的方式来定义的，他有两种值构造子，一种是[],一种是:这个中缀调用的函数, 它接受两个参数一个是需要存放的data a，另外一个剩余部分的list。
在函数式编程里递归的方式是常态，当然现在暂时对于这个定义可能还不能完全看懂，let's move on!
作为函数式编程，我想哪怕很多人没有接触过也直到高阶函数或者是函数指针，一般来说最常用的就是map 和 filter了，当然haskell里也有
map (\x -> x +1) [1,2,3]
-- [2,3,4]
-- 因为concat 和 map其实联合使用的概率实在太大了，方便起见，有函数concatMap = concat (map func list)
hey, 是熟悉的lamada表达式, filter同理，在后面讲高阶函数的时候再细说吧。
很好现在解决问题的工具终于准备的差不多了， 终于可以开始解决初中数学题了，啊不大概是小学。
permutation :: [a] -> [[a]] --------------------这是a 代表任意类型（随便用啥字母都可以），这样方便arrange可以应用到不同的类型,请脑补成Child类型
permutation [] = [[]]
permutation (x:xs) = concatMap (insertAll x) (permutationxs)
where
insertAll v [] = [[v]]
insertAll v (x':xs') = [(v:x':xs')] ++ map (x':) (insertAll v xs')
稍微的解释一下，当我们在haskell中在一个函数中逻辑过于长，想要拆分成两个函数，或者某个自变量部分过于长的时候可以使用where子句，这样可以把内部使用的辅助函数和辅助变量封装在函数内部，提高代码的可移植性和可读性。
这里我们可以看到函数式编程在对于解决数学问题上使用起来真的是非常直接， 只需要把思路像自然语言那样，通过算术逻辑的组合就可以简单的得到结果！效果很不错，现在你可以尝试着用c系列语言写一下，我尝试了一下大概是15行左右的逻辑，可以看到，从代码量上来说，函数式的方式确实很酷。但是这样的代码在阅读的时候需要阅读者首先必须先熟悉算法的基本思想，否则的话可读性简直是糟糕到了极点了。
值得一提的是排列还有另外一种方法，假设位子已经排定，那么第一个位置可以插入4种不同的元素，第二个位置3种，大家可以尝试下用这种思路来写, 不过需要用到列表生成式，就放到后面来讲吧。
网友评论