Lisp Taiwan

[omusico]

致力於分享及彙整 Lisp 相關資料與知識

http://lisp.tw/

[omusico]

寫給我們的函式編程

http://lisp.tw/2013/02/17/functional-programming-for-the-rest-of-us/

omusico於 2013年5月3日星期五UTC+8下午1時38分05秒寫道：

[omusico]

get the minimum element in list using erlang

http://cctg.blogspot.com/2013/04/get-minimum-element-in-list-using-erlang.html?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+Cctg+%28cctg%29

--
您已訂閱「Google 網上論壇」的「Erlang_Taiwan」群組，因此我們特別傳送這封郵件通知您。
如要取消訂閱這個群組並停止接收來自這個群組的郵件，請傳送電子郵件到 erlang_taiwa...@googlegroups.com。
如要在此群組張貼留言，請傳送電子郵件至 erlang...@googlegroups.com。
請前往以下網址造訪這個群組：http://groups.google.com/group/erlang_taiwan?hl=zh-TW。
如需更多選項，請前往：https://groups.google.com/groups/opt_out。
 
 

[黃耀賢 (Yau-Hsien Huang)]

omusico 兄難得這麼有閒情看點 Lisp 方面的文章。説到其中

某篇提到的 Tetris 格式的形式系統之哲思，還真是如此。

學久了學熟了，就發現我們在學的、在用的許多東西是著重

在結構上。

說回到上篇討論最小數字的搜尋，仿照快速排序的前後段拆解，

看似有效率，但仔細想想細部的語意：當過程中收集著各方

較大的數或較小的數的時候，不正是直線走過了一次了嗎？

而最初的求最小值，也就是直線走過一次而已；同時求最大值

和最小值，也可能是直線走過一次或二次。說來，單純的解法

的時間複雜度就是 O(n) ，而且不必在乎究竟是走過一次或

走過二次。但換為快速排序風格，卻讓解法時間複雜度降級為

O(n log n) 。

我倒覺得，文章中無意點出的函數語言程式之美，在於揭露

一種近似於數學的型式：

    min([a, b, c, d, ...])

    = min([ min([a,b]), min([c]), min([d, ...]) ])

    = min([ min([a]), min([b]), min([c]), min([d]), ... ])

    = ......

求最小值的函數，特質恰好是非常適合分散運算。

2013/5/3 omusico <omu...@gmail.com>

--

Best Regards.

--- Y-H. H.

[omusico]

主要是覺得在分散式的計算上list+函數語言在原型上
就有天生計算伸縮的特性 想請教ㄧ下 如果遞迴+lazy
是否就沒有記憶體1不足問題....erlang這個部份的處理
似乎需要人工多去測試才有可避免

[黃耀賢 (Yau-Hsien Huang)]

erlang 基本是不 lazy 的執行方式，要特別寫 lambda expression 來定義出 lazy evaluation 。

    appendLazy(Xs, Ys) ->

        fun() -> append(Xs, Ys) end.

按照邏輯， lazy evaluation 的確避免及早遞迴而撞到記憶體邊界的問題。

另外說到遞迴遭遇到記憶體障礙，我想都是在無窮迴路中產生累積的資料，將記憶體用完。

以下列程式來看， f/1 是尾端遞迴，執行時沒有累積記憶體用量的情況， g/1 則會用到

Heap不足：

    f(N) -> A = 1, f(N).

    g(N) -> A = 1, g(N), B = 2.

程式是會寫錯的。若要有什麼工具防止人寫錯遞迴程式，應該是要去找些什麼工具能檢查

遞迴程式會停止。但是我不知道有什麼工具可用。

2013/5/4 omusico <omu...@gmail.com>