排列函數

排列和組合是很容易處理的問題。但不知道為什麼，在資訊科系學寫程式之後，排列卻變成相當難的問題。難的地方是在像 C 語言的程式步驟和資料型態上，要考慮很多額外的東西，也遇到很多小麻煩。因此，「取一列資料的全部排列情況」變成一項我一直不會寫程式解決的問題。

而使用像 Haskell 這樣的函數程式語言，將過去所學的知識加以翻覆、折疊，重新整理出一條順暢的思考路線。我最近寫出的排列函數如下；再下去，讓我解釋一下函數構成的想法。

allPermu :: (Eq a) => [a] -> [[a]]
allPermu xs = compact rs
 where rs = map (map (\x -> xs!!x)) (allPermu' [0..((length xs)-1)])

allPermu' :: (Eq a) => [a] -> [[a]]
allPermu' [] = [[]]
allPermu' xs = concat (map f xs)
 where f = \x -> map (x:) (allPermu' (filter (x/=) xs))

compact :: (Eq a) => [a] -> [a]
compact [] = []
compact (x:xs) = if any (x==) xs then compact xs
          else x : compact xs

解析

1. allPermu' 函數：取一列資料的全部排列情況

首先，我覺得取一列資料，如 [4, 3, 4, 5] 的全部排列情況，就是先考慮 4, 3, 4, 5 各數字，將原列資料的這個數字拿掉，求剩下的一列資料的全部排列情況，然後將這個數字都擺在全部排列情況的每一項前面。就這個例子來說， 4, 3, 4, 5 分別要做一次這樣的動作。只考慮 3 ， 3 要和剩下的 [4, 4, 5] 的全部排列組成。 [4, 4, 5] 的全部排列有 [4, 4, 5], [4, 5, 4], [5, 4, 4] ，讓 3 擺在每一項的前面就產生 [3, 4, 4, 5], [3, 4, 5, 4], [3, 5, 4, 4] 這些。

我先要有一個函數是 f = \x -> map (x:) (allPermu' (filter (x/=) [4, 3, 4, 5]) ，是一個函數名為 f ，接到一個參數叫 x ，就把 [4, 3, 4, 5] 中不等於 x 值的項目取出成一列，用一個取全部排列的函數名叫 allPermu' 求少了 x 的全部排列情況。 (只是 allPermu' 在此還沒講它怎麼寫。) 然後，用 map 函數將 (x:) 套到少了 x 的全部排列的每一項前面。這種想法很簡單，對一列資料的每一項，都先把少了那一項的其他資料做排列，所得到的全部排列情況再把少掉的那一項套在前面。

於是，可以說 allPermu' [1, 2] = map f [1, 2] ，再解開就是

map f [1, 2] = [f 1, f 2] = [map (1:) (allPermu' (filter (1/=) [1, 2])),
                         map (2:) (allPermu' (filter (2/=) [1, 2]))]
filter (1/=) [1, 2] = [2]
filter (2/=) [1, 2] = [1]
allPermu' (filter (1/=) [1,2]) = allPermu' [2] --這裡細節省略，我們知道 [2] 全部排列就是 [[2]]
allPermu' (filter (2/=) [1,2]) = allPermu' [1] = [[1]]
map f [1, 2] = [ map (1:) [[2]] , map (2:) [[1]] ]
         = [ [[1, 2]] , [[2, 1]]]

最候出現答案了，但是資料結構的深度加一層。如果把 allPermu' 函數寫成以下這樣......

allPermu' xs = map f xs
            where f = \x -> map (x:) (allPermu' (filter (x/=) xs))

這是有麻煩的程式。因為當 allPermu' 處理 xs 一次，展開成右邊算式 map f xs 得到的答案會讓資料結構加一層。本來對 [1, 2] 我們想求的答案是 [[1, 2], [2, 1]] ，但是按照前面的計算結果，答案卻是 [[[1, 2]], [[2, 1]]] 。雖然算得出答案，但是表達一列資料的層次越來越深。這時我們需要一個函數讓 [[[1, 2]], [[2, 1]]] 變成 [[1, 2], [2, 1]] ，把資料結構層次降低一層。有一個預設的函數叫 concat 可以做這件事情，如果有一列資料是 [a, b, c, ...] 而 a, b, c, ... 是另外幾列資料， concat [a, b, c, ...] 是把 a, b, c, ... 這幾列資料銜接在一起，於是資料結構的層次減低一層。所以，使用 concat 把 allPermu' 寫得好的程式如下：

allPermu' xs = concat (map f xs)
            where f = \x -> map (x:) (allPermu' (filter (x/=) xs))

上面這個 allPermu' 是遞迴的情況。而遞迴程式應該要包含遞迴部份和基底部份。把基底和 allPermu' 函數的型態加進去，完整的 allPermu' 函數就是：

allPermu' :: (Eq a) => [a] -> [[a]]
allPermu' [] = [[]]
allPermu' xs = concat (map f xs)
            where f = \x -> map (x:) (allPermu' (filter (x/=) xs))

然而， allPermu' 有個問題是，如果處理的資料列中有重覆資料，因為 filter (x/=) xs 比對 x 值是否相同的作用，會讓 allPermu' [4, 4, 5] 求出不對的答案。即使如此，至少 allPermu' 函數處理一列每個項目都彼此不同的資料是做得對的。後來我想，任何一列可能有重複項目的資料背後都藏了另一列項目彼此不同的資料，就是由原列每一個項目存在的位置編號。例如， [4, 4, 5] 對應到它們的位置編號 [0, 1, 2] 。以下的 allPermu 函數，在處理任何一列資料時，先取出該列資料的一列位置編號，用 allPermu' 函數產生位置編號的全部排列，再將這些排列轉換為原資料。

2. allPermu 函數：產生任何一列資料的全部排列情況

在 Haskell 寫 [0..9] 可以得到 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] ，是取得等差遞增序列的特殊語法。對任何一列資料，例如 [4, 3, 4, 5] ，可以寫 [ 0 .. ((length [4, 3, 4, 5]) - 1) ] 產生從 0 開始的遞增序列，也就是 [4, 3, 4, 5] 的位置編號 [0, 1, 2, 3] 。

於是， allPermu' [0..((length [1, 2])-1)] 是 [1, 2] 位置編號的全部排列情況， [[0, 1], [1, 0]] 。接著要將 [[0, 1], [1, 0]] 轉換成 [[1, 2], [2, 1]] 。用 map (\x -> [1,2]!!x) [0, 1] 可以做到這件事情。給一個數字 x ， [1, 2] !! x 就是在 [1, 2] 列中取第 x 個位置的項目。所以，以下的程式可以將 [[0, 1], [1, 0]] 轉換成 [[1, 2], [2, 1]] ：

map (map (\x -> [1, 2]!!x)) [[0, 1], [1, 0]]

第一個 map 將第二個 map 伴隨其參數的段落，即 map (\x -> [1, 2]!!x) ，套到 [[0, 1], [1, 0]] 的每一個項目。接著對 map (\x -> [1, 2]!!x) [0, 1] 來說，是將函數 \x -> [1, 2]!!x 套到 [0, 1] 的每一個項目。所以基本上， allPermu 函數可以寫成：

allPermu xs = rs
           where rs = map (map (\x -> xs!!x)) (allPermu' [0..((length xs)-1)])

但是，考慮 allPermu [4, 3, 4, 5] 會發現出現一些重複的項目，例如，雖然 [0, 1, 2, 3] 和 [2, 1, 0, 3] 的確是兩種不同的排列情況，卻都轉換成 [4, 3, 4, 5] 。於是第三個函數 compact 是將多個重複項目刪掉。 compact 函數在 Haskell 是很普遍的程式處理方式，在此省略其介紹。

3. 結論

本篇由一件以 Haskell 撰寫的全部排列函數，解析一般的處理排列問題的遞迴解題方式。求一列資料的全部排列，是對資料列中的每一項，先求其他項目的全部排列，再將這一項分配結合到其他項目全部排列的每一項之前。透過函數程式語言的寫作方式，可以讓我們重新抓到人們解決問題的直覺能力，使我們從以往局限在程式執行步驟數量的思考方式中得到解脫。

函數語言版本的費氏數列程式

費氏數列 (Fibonacci's numbers) 是 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 這樣的數列，其中每個數為前二個數的和，除了最前面的底數 0, 1 外。

小小的費氏數列程式很好寫，看起來也很好執行，以 C 語言為例：

n_2 = 0; n_1 = 1;
if (n == 0)
    fn = n_2;
else if (n == 1)
    fn = n_1;
else
    for (i=2; i<n; i++) {
        fn = n_2 + n_1;
        n_2 = n_1;
        n_1 = fn;
    }

最後 fn 為答案。但 C 程式版本其實不好執行，若指定的費氏項數稍大，而程式中的變數是整數或長整數，就會溢位。

函數語言 Haskell 寫出來的比較可愛：

fibNum :: (Integral a) => a -> a
fibNum 0 = 0
fibNum 1 = 1
fibNum (n+1) = fibNum (n-1) + fibNum n

雖然沒有溢位問題了，但是打個 fibNum 100 跑得真久，因為遞迴的計算量很大。

但函數語言的好處是，許多程式可用累積變數 (aggregating parameters) 改寫成線性版本，改善計算效率。在此，例如：

fib :: (Integral a) => a -> a
fib n = fib1 n 0 1

fib1 :: (Integral a) => a -> a -> a -> a
fib1 0 x _ = x
fib1 1 _ y = y
fib1 (n+1) x y = fib1 n y (x+y)

打個 fib 100 很快就跑出答案為： 354224848179261915075 。漂亮！

在此可見程式語言的特性，除了語法可愛和簡潔之外，在可優化的容易程度是特別有價值的。

想要探索更深入的價值，請積極參與微程式資訓技術研討會¹並參閱投影片。

---

¹微程式資訊技術研討會是微程式資訊股份有限公司的內部會議。

函數語言處理氣泡排序法

在碩士班期間擔任幾年的大學基礎程式設計課程的實習助教，在講台上解題，講了氣泡排序法幾乎有十次（對不同班、不同年級）。

for (i=0; i<N; i++)
        for (j=0; j<N-i-1; j++)
                if (A[j] > A[j+1]) {
                        temp = A[j];
                        A[j] = A[j+1];
                        A[j+1] = temp;
                }

二個迴圈洽好代表二層次的工作：裏層負責排列順序、外層負責控制執行次數和調整排序範圍。

用 Haskell 函數語言寫氣泡排序，是將二個層次功能做好，然後組合起來。首先是氣泡調整的部份（如下方的 bubble）， bubble 函數要將一列資料由小（左）排到大（右），而且要從右邊開始向左調整順序，將較小的數字往左邊推。這和上述的普通程式處理方向相反。

bubble :: (Ord a) => [a] -> [a]
bubble [x] = [x]
bubble (x:xs)
        | x > y = y:x:ys
        | otherwise = x:y:ys
        where (y:ys) = bubble xs

次數控制的部份（如下方的 loop）， loop 函數一方面要先將某個 f 函數套到一串數列（xs）上、取回的結果（y:ys）再將 f 函數套上去；另一方面， loop 函數控制執行次數，藉由將 f 函數再次套到上次已經套過 f 函數的結果（y:ys）時，是將第一個數字（y）取出，將 f 函數套在剩餘的數列（ys）上。每次套上 f 函數之後，就取出數列的一個數字，於是剩下的數列越來越小，直到剩下空數列（[]）。

loop :: (Ord a) => ([a] -> [a]) -> [a] -> [a]
loop f [] = []
loop f xs = y : loop f ys
        where (y:ys) = f xs

接下來，氣泡排序程式（如下方的 bubbleSort），是將 loop 函數和 bubble 函數放在一起。

bubbleSort :: (Ord a) => [a] -> [a]
bubbleSort = loop bubble

執行情況：

GHCi, version 6.8.3: http://www.haskell.org/ghc/  :? for help
Loading package base ... linking ... done.
Prelude> :load "d:/code/hsBubbleSort/bubbleSort.hs"
[1 of 1] Compiling Main             ( d:/code/hsBubbleSort/bubbleSort.hs, interpreted )
Ok, modules loaded: Main.
*Main> bubbleSort [3,2,9,7,8,5,4]
[2,3,4,5,7,8,9]
*Main> bubbleSort [5]
[5]
*Main> bubbleSort []
[]
*Main>

寫parser多簡單?

為了處理 Jabber/XMPP 的實作，勢必要考慮到 parser。

根據 Wikipedia 的說明，parser是指將一串輸入文字建立為 parse tree 的功能。根據文法，字串無法剖析為 parse tree 代表剖析錯誤。

用 Haskell 寫 parser 似乎比較簡單。 (?)

Parse tree

一般來說，(binary) tree 是指：

1. 「空無」情況是 tree ，或是


2. 以一項物件為基礎，擁有左子項和右子項，二個子項也是 tree 。

在 Haskell 定義 tree 資料結構為

data Tree = A | B | Bin (Tree, Tree)
deriving Show

看起來已經滿足一個 parse tree 的構成。

Parser

Parser 是一個函數，其輸入為一串資料，並輸出一些可能的 parse tree 和剩餘未 parsed 的資料。因此宣告 parser 的資料型態為：

type Parser a b = [a] -> [(b, [a])]

其中， a 是輸入資料的型態， b 是 parse tree 的型態。

根據 Parser a b 的型態規範，可以定義各式各樣的 parser 。例如：

永遠 parsed 的 parser 叫做 succeed

succeed :: Parser a ()
succeed xs = [((), xs)]

永遠 false-parsed 的 parser 叫做 fail

fail :: Parser a b
fail xs = []

讀取指定字元的 parser 叫做 lit (literal parser)

lit :: Eq a => a -> Parser a a
lit x (y:xs) | x == y = [(y, xs)]
lit x _ = []

執行情況：

lit 對字串 "Babcd" 要 parse 一個 `B' 字元，就得到一個 parsed `B'，並剩下 "abcd" 字串。

lit 對字串 "Aabcd" 要 parse 一個 `B' 字元， parse 失敗，於是得到一個 empty list [] 代表 false-parsed 。

(待續)

erlang 會成為下一個java ?

erlang 會成為下一個java ?
文章連結

其實應該說是functional language 的時代快來臨了,或是已經來臨
文章連結1
文章連結2
文章連結3

Erlang-China
http://www.erlang-china.org/

The factorial's tail recursive

Erlang:

-module(test).
-export([fac/1]).
fac(N) -> fac(N,1).

fac(0,A) -> A;
fac(N,A) -> fac(N-1,N*A).
--------------------------------
Haskell:

module Fac
where

fac(n)=facit(n,1)
facit(0,m) = m
facit(n,m)=facit(n-1,n*m)

恩! 第二次聽這個理論,似乎又更清楚了

lazy:
1.
expressions which are not needed to determine the answer to a problem are not
evaluated

這一點;下一週我應該更清楚的詢問
a.這跟recursion 有關嗎?事實上recursion 跟這個描述有點類似
b.沒有答案,要如何偵測結果的對錯,比如型態的問題,或是溢位的問題
在我看到 Yet Another Haskell Tutorial 第三章快結束時 我想通了
2.
implementation of non-stictness
=====================================================
有時間該常上的網站(Lamdba the ultimate)
http://lambda-the-ultimate.org/