2008年7月31日 星期四

[Derivation] Plateau

這兩天在寫一個題目,要求一個list中最長的等價區段。也就是要找出list中最多有多少個相同且緊鄰的elements。

一開始我的作法很簡單。我先把list根據相同且相鄰的element分割成若干個list,再把全部放進一個list裡面。也就是[a,b,b,c,c]會變成[[a],[b,b],[c,c]]。然後再去計算其中每一個list的長度,最後在用foldr去取極大值,這樣就結束了。

     foldr max 0 ○ map length
= {map length = foldr (\x xs -> (length x) : xs) []}
     foldr max 0 ○ foldr (\x xs -> (length x) : xs) []
= {by fold-fusion}
      foldr (\(x:xs)->max (length x) xs) 0

      foldr max 0 ○ map length ○ refinement
= {see above reasoning}
      foldr (\(x:xs)->max (length x) xs) 0 ○ refinement

至此,問題就突然變成refinement要怎樣定義。一開始我的想法是先用fold去define refinement。也就有了:

cmb x xs =
  if x == ((head.head) xs)
     then (([x] ++ head xs):(tail xs))
     else ([x] : xs)

refinement = foldr cmb [[0]]

原式也因此變成了

plateau = foldr maxl 0 ○ foldr cmb [[0]]

然後這裡應該要在用一次fold fusion去把兩個fold fuse成一個。但是因為cmb有if-then-else,而fusing時我不太確定那個部份要怎樣去處理。所以這個方式就先按下不表。等之後精神比較健全的時候再來重心想一次。

接著,先回到refinement尚未定義的狀況。因為refinement的需求,我們知道refinement也可以用unfold來define。而且這樣整個式子就變成了fold ○ unfold。這樣一來就可以使用hylomorphism來消去中間產生的list of list。因此:

gen (x:xs) = < takeWhile (== x),dropWhile (== x) > (x:xs)

refinement = unfoldr (== 0) gen

plateau'
= {see above definition}
    foldr maxl 0 ○ unfoldr (== 0) gen
= {hylomorphism}
     if ((==0).length) a
     then 0
     else let (n,a') = (\(x:xs)->< takeWhile (== x), dropWhile (== x) > (x:xs)) a
         in (\x xs->max (length x) xs) n (plateau2 a')

2008年7月16日 星期三

[Haskell] unit ( )

很早就知道nullary tuple,也就是unit ( )的存在。
不過一直以來都不太清楚那是做什麼的,只隱約知
道type ( )有兩個elements : unit ( ) 和 bottom _|_ 。
雖說大概可以猜說這個unit type是用來描述Relative
Nothing和Absolute Nothing這樣的概念。但是也
一直想不太到實際上這要做什麼。

不過前幾天在書上看到一段在講unit。其中也有舉了
一個簡單的例子。看完以後有種恍然大悟的感覺。

圓周率一般的寫法如下

pi :: Float
pi = 3.14159

這樣當然是正確的,沒什麼不好現在我們加入unit。

pifun :: ( ) -> Float
pifun ( ) = 3.14159

這樣有什麼好處呢?如此一來我們就有一個function
可以用。比起原本的pi,pifun因為是function,所以
我們可以有更大的彈性以及更好的一些性質。例如
說我們現在可以對pifun用compose,而不在只是
把pi當作value餵給另一個function。

(*2).(pifun)
(*2) pi


最後,補充一下有關Absolute Nothing和Relative
Nothing的事情。在Ontology(形上學)中,主要是
以Being(存在)為探討的主題。而相對於Being的概念,
就有了Nothing(無)的概念。後來隨著各代哲學家的研究,
出現了Absolute Nothing(絕對無)和Relative Nothing
(相對無)這兩種略有不同的Nothing。AN是相對Being
的東西,他相當於"完全沒有存在任何東西"。RN則比較
像是欠缺什麼,也有點像是比較不嚴謹的AN。一個顯著
的例子就是 Φ 和 { } 之間的差別:
Φ 是沒有任何東西。
{ } 有一個空的東西。

2008年7月10日 星期四

Something Diff.

之前好像很多文章都是比較工具有關的文章
不過,隨著在scm老師那裡蝦混的時間越來越長
好像接觸的東西也漸漸無關了那些工具相關的東西

因此,這樣以安裝與使用為主題的post方向
好像也漸漸開始應該要廢除了

另一方面
好像也該用講故事的方式
來確保自己是真的讀/看懂了某些東西

所以,希望也會可以多寫一些理論知識性的東西
順便練練英文(? XD)

FLOLAC'08 (cont.)

一個小時前考完試了
去年我沒有考
所以沒有可以類比
不過今年我覺得難度還不錯
不會太難也沒有太簡單

不過FP&T最後幾題都好花時間和版面的說

但是話說回來
derivation的部份,畢竟是看很多次的東西
寫起來相當順手呀
別人這裡可能多少都有卡好一會兒
不過我反而是多蠻多時間去想別的科目

整體而言
雖說作業東辣西辣的空掉一堆沒寫
但是考試卻相當順手
上課也學到很東西
也知道自己哪裡尚且不足
相當超值的課程
(不過有點累就是了)

明年要是有錢有閒的話
再來參加好了 XD

2008年7月9日 星期三

FLOLAC'08

今天是今年的FLOLAC'08最後一天的課程了

今年整體而言似乎比去年輕鬆一點
大概是因為前半的課我都聽過一部分了
就算是(依舊)不熟的accumulating parameter
也因為去年有點印象
感覺順遂很多
而去年慘兮兮的 fold-fusion
今年更是順到整個心情大好
logic的部份也是整個多懂很多
去年蠻都只是照著rule依樣畫狐狸

不過今年的semantics就有點糟糕了 Orz
給的說法都太廣泛了
好像都聽的懂,但是真要說瞭解
卻又說不出個所以然來
果不其然,最後看到作業時都只能楞在那裡
口中也只能發出"哈哈"之類的聲音

第二個禮拜的重心我更是慘兮兮呀
大概都知道在做啥
可是沒多少聽的懂
果然英文還是我的致命傷呀 O_Q

整體而言
今年的課程感覺都是在整理過去這一年多
從Mu老師那裡,還有paper上面看到或是接觸到的東西
把過去看過的東西給予一套形式上的歸納/說法
不過誠如自己一直以來知道的
基礎還是相當薄弱
雖說以自己身為升大三的學籍身份來說
似乎可以釋懷一點
不過還是因此覺得更應該好好加強一下基礎

書堆+3
總計...好幾本 XD