Posts Tagged ‘haskell

06
ม.ค.
10

แก้โจทย์ L-99:Ninety-Nine Lisp Problems P13

P13 (**) Run-length encoding of a list (direct solution).
Example:
* (encode-direct ‘(a a a a b c c a a d e e e e))
((4 A) B (2 C) (2 A) D (4 E))

ข้อนี้ให้ encode ลิสต์โดยแปลงให้กลายเป็น ลิสต์ของลิสต์ที่มีค่าแรกคือความยาวของตัวที่ซ้ำอีกตัวก็คือค่าที่ซ้ำ แต่ถ้าอันไหนยาวแค่ 1 ก็ไม่ต้องให้มีตัวเลขบอกจำนวน เช่น B กับ D

ข้อนี้ สำหรับ Haskell วันนี้ จะสร้าง data type ขึ้นมาใหม่ เพื่อเก็บข้อมูลที่เข้ารหัส เพราะ ว่า Haskell มันเก็บ ลิสต์ที่มี type ต่างกันปนกันไม่ได้

Haskell

import Data.List
data LengthEncode a =  L a |  LS Int a
                        deriving (Show)

encode::(Eq a)=>[a]-> [LengthEncode a]
encode [] = []
encode xs = map subEncode (zip (map length (group xs)) (map head (group xs)))
                where
                        subEncode x = if ((fst x) == 1)
                                        then
                                                (L (snd x))
                                        else
                                                (LS (fst x) (snd x))

สร้าง data type ชื่อ LengthEncode a โดยมี constructor 2 แบบคือ L a สำหรับกรณีความยาวแค่ 1 และ LS Int a สำหรับกรณีที่เหลือ

ตรงส่วนของฟังก์ชัน encode เราจะใช้ map เข้ามาช่วย ตรง (zip (map length (group xs)) (map head (group xs))) เราจับ xs ที่เข้ามาไป เรียกใช้ group เพื่อให้ได้ list แบบโจทย์ข้อ P09 แล้ว มาใช้ map length จะได้ลิสต์ของจำนวนซ้ำ ส่วน map head จะเอาแค่ตัวแรกตัวเดียว เสร็จแล้วจับมา zip รวมกันจะได้ list ของ tuple ที่ตัวหน้าเป็นจำนวน ตัวหลังเป็นอิลิเมนต์ที่ถูกเข้ารหัส แล้วสุดท้ายใช้ map subEncode โดยที่ subEncode จะแปลงจาก tuple ไปเป็นข้อมูลแบบ LengthEncode a จะใช้ L หรือ LS ก็แยกตามความยาว

Erlang

-module(pack).
-export([encode/1]).
pack ([]) ->    [];
pack (L)  ->    [H|_] = L,
                A = lists:takewhile(fun(X)-> X == H end,L),
                B = lists:dropwhile(fun(X)-> X == H end,L),
                [A | pack(B)].
encode([]) -> [];
encode(L)  -> ELEMCOUNT = lists:map(fun(X)->[H|_] = X,H end,pack(L)),
              COUNT = lists:map(fun erlang:length/1 ,pack(L)),
              ZIP = lists:zip(COUNT,ELEMCOUNT),
              lists:map(fun(X)->{C,E} = X, (if C == 1 -> E; C > 1 -> [C,E] end) end,ZIP).

Lisp

(defun my-filter (L A R)
        (if L
                (if (equal (first L) A)
                        (my-filter (rest L) A (cons (first L) R))
                        (cons R L)
                )
                (cons R L)
        )
)
(defun pack (L)
        (if L
                (cons (first (my-filter L (first L) nil)) (pack (rest (my-filter L (first L) nil))))
                nil
        )
)

(defun encode (L) (map 'list (lambda (X) (if (eql (length X) 1) (first X) (cons (length X) (cons (first X) nil)))) (pack L)))
05
ม.ค.
10

แก้โจทย์ L-99:Ninety-Nine Lisp Problems P09

วันนี้ทำข้อ P09

P09 (**) Pack consecutive duplicates of list elements into sublists.
If a list contains repeated elements they should be placed in separate sublists.

Example:
* (pack ‘(a a a a b c c a a d e e e e))
((A A A A) (B) (C C) (A A) (D) (E E E E))

ข้อนี้ จะจับอลิเม้นที่เหมือนกัน ที่อยู่ติดๆกันให้เป็นลิสต์ใหม่โดยผลลัพธ์สุดท้ายก็คือลิสต์ของลิสต์ที่จับตัวที่ซ้ำๆมาอยู่ด้วยกันแล้วนั่นเอง

ข้อนี้ถ้าใช้ takeWhile กับ dropWhile มาช่วยดึงเอาelementที่ซ้ำๆที่ติดกันออกมาจะง่ายหน่อย แต่จะยังไม่ใช้จะเขียนฟังก์ชันขึ้นมาช่วยเองอีกตัวใช้แยกลิสต์ที่เป็น input ออกเป็น 2 ส่วนคือ ส่วนที่ซ้ำ กับ element ที่เหลือที่หักส่วนที่ซ้ำออก ส่วนฟังก์ชัน pack หลักๆนั้นก็แค่ทำการเรียกฟังก์ชันที่ใช้แยกelementที่ซ้ำก็จะได้listของelementแล้วก็เอาลิสต์นั้นมาต่อๆกับผลลัพธ์ที่ได้จากการเรียกซ้ำส่วนที่เหลือของลิสต์

Haskell

pack::(Eq a)=>[a]->[[a]]
pack [] = []
pack xs = (fst (myFilter xs (head xs) [])):(pack (snd (myFilter xs (head xs) [])))
                where
                        myFilter [] a rs = (rs,[])
                        myFilter (x:xs) a rs | x == a = myFilter xs a (a:rs)
                                                        | otherwise =  (rs,(x:xs))

ส่วน Haskell จะต่างกับ Erlang และ Lisp นิดหน่อยคือ myFilter จะส่งผลลัพธ์ที่ได้มาเป็น tuple

Erlang

-module(pack).
-export([pack/1]).
myfilter ([],_,R) -> [R];
myfilter ([L|T],A,R) when L == A -> myfilter (T,A,[L|R]);
myfilter (L,_,R) -> [R|L].
pack ([]) ->    [];
pack (L)  ->    [H|_] = L,
                                   [A|B] = myfilter(L,H,[]),
                                   [A | pack(B)].

Lisp

(defun my-filter (L A R)
        (if L
                (if (equal (first L) A)
                        (my-filter (rest L) A (cons (first L) R))
                        (cons R L)
                )
                (cons R L)
        )
)
(defun pack (L)
        (if L
                (cons (first (my-filter L (first L) nil)) (pack (rest (my-filter L (first L) nil))))
                nil
        )
)
04
ม.ค.
10

แก้โจทย์ L-99:Ninety-Nine Lisp Problems P08

วันนี้ทำข้อ P08

P08 (**) Eliminate consecutive duplicates of list elements.
If a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed.

Example:
* (compress ‘(a a a a b c c a a d e e e e))
(A B C A D E)

จากโจทย์คือเขียนฟังก์ชัน compress เปลี่ยนลิสต์ที่มีสมาชิกที่ซ้ำๆกัน และอยู่ติดกัน ให้เหลือเพียงแค่ตัวเดียว ข้อนี้ไม่ยาก เงื่อนไขมี 3 แบบ คือ เมื่อ ลิสต์มีสมาชิกแค่ตัวเดียวให้ ส่งค่านั้นเป็นผลลัพธ์ ถ้าเป็นกรณีอื่นให้เอาสมาชิกตัวที่หนึ่งกับสอง มาเทียบกัน ถ้าเท่ากัน เราจะเรียกซ้ำฟังก์ชัน แต่ตัดสมาชิกตัวแรกสุดออก ถ้าสมาชิกตัวที่หนึ่งกับสองไม่เท่ากัน เราจะเอาสมาชิกตัวที่หนึ่งมาต่อกับผลลัพธ์ที่ได้จากการเรียกซ้ำโดยตัดสมาชิกตัวแรกออก

Haskell

compress::(Eq a) =>[a]->[a]

compress [x] = [x]
compress (x:y:xs)
                | x == y = compress (y:xs)
                | otherwise = x:compress(y:xs)

Erlang

-module(compress).
-export([compress/1]).

compress ([L|[]]) -> [L|[]];
compress ([L|[M|T]]) when (L == M) -> compress ([M|T]);
compress ([L|T]) -> [L | compress (T)].

Lisp

(defun compress (L)
        (if (eql (second L) nil)
                L
                (if (eql (first L) (second L))
                        (compress (rest L))
                        (cons (first L) (compress (rest L)))
                )
        )
)
29
ธ.ค.
09

แก้โจทย์ L-99:Ninety-Nine Lisp Problems P02-P05

วันนี้จะมาแก้ข้อ P02 ถึง P05 เมื่อวานลืมใส่ url web ที่รวมโจทย์ อยู่ที่เว็บนี้ http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html

เริ่มที่ P02

P02 (*) Find the last but one box of a list.
Example:
* (my-but-last ‘(a b c d))
(C D)

ให้เขียนฟังก์ชัน ดึง ตัวสุดท้ายและตัวก่อนสุดท้ายออกมา ก็ใช้ recursive แบบเมื่อวานแต่เราจับ pattern ที่ list มีสมาชิก 2 ตัวแล้วค่อยส่งค่า 2 ตัวนั้นเป็นผลลัพธ์ของฟังก์ชัน

Haskell

myButLast::[a]->[a]

myButLast ([x,y]) = ([x,y])
myButLast (_:xs) = myButLast xs

Erlang

-module (lninenine).
-export ([myButLast/1]).

myButLast([X|[Y | []]]) -> [X|[Y|[]]];
myButLast([_|T]) -> myButLast(T).

Lisp (Clisp)

(defun my-but-last (L)
        (if (rest (rest L))
            (my-but-last (rest L))
            L
        )
)

ข้อ ต่อไป P03

P03 (*) Find the K’th element of a list.
The first element in the list is number 1.
Example:
* (element-at ‘(a b c d e) 3)
C

ข้อนี้ให้เขียนฟังก์ชันรับค่า list กับตัวเลขบอกว่า ลิสต์ตัวที่เท่าไหร่แล้ว ก็ให้ฟังก์ชันส่งสมาชิกของลิสต์ตัวที่เท่านั้นออกมา ข้อนี้เราจะ recursive ไปแล้วก็ลดค่าของ parameter ตัวที่สองลงไป และค่อยๆตัดสมาชิกตัวแรกของลิสต์ออก จนเมื่อค่าของ parameter ตัวที่สองเป็น 1 เมื่อไหร่ เราก็จะส่งค่า สมาชิกตัวแรกของลิสต์ ณ ขณะนั้นออกมา

Haskell

elementAt::[a]->Int->a

elementAt (x:_) 1 = x
elementAt (_:xs) n = elementAt xs (n-1)

Erlang

elementAt ([H|_],1) -> H;
elementAt ([_|T],N) -> elementAt (T,(N-1)).

Lisp

(defun element-at (L N)
        (if (= 1 N)
            (first L)
            (element-at (rest L) (- N 1))
        )
)

ข้อต่อไป P04

P04 (*) Find the number of elements of a list.

ข้อนี้ให้เขียนฟังก์ชันสำหรับหาจำนวนสมาชิกของลิสต์ ใช้วิธี recursive เพื่อนับ เราจะสร้าง  ฟังก์ชันเข้ามาช่วยเพื่อนับ เป็นฟังก์ชันที่รับค่าเริ่มต้นในการนับ เราจะบวกค่านี้ไปเรื่อยๆจนกว่าจะพบว่าลิสต์เป็นลิสต์ว่าง เราจะใช้ค่านี้เป็นผลลัพธ์ของฟังก์ชัน ส่วนฟังก์ชันหลักเราจะเรียกฟังก์ชันนี้อีกที โดยส่งค่า 0 เป็นค่าเริ่มต้นการนับ

Haskell

elementNum::[a]->Int
elementNum xs = elementNum' xs 0
                             where
                                     elementNum' [] n = n
                                     elementNum' (_:xs) n = elementNum' xs (n+1)

Erlang

-module (lninenine).
-export ([elementNum/1]).
elementNum (L) -> elementNum(L,0).
elementNum ([], N) -> N;
elementNum ([_|T], N) -> elementNum (T, (N+1)).

Lisp

(defun element-num-count (L N)
        (if L
            (element-num-count (rest L) (+ N 1))
            N
        )
)

(defun element-num (L)
        (element-num-count L 0)
)

สุดท้ายของวันนี้ P05

P05 (*) Reverse a list.

คือเขียน function เรียง สมาชิกใน ลิสต์ใหม่จากหลังไปหน้า ข้อนี้จะมีฟังก์ชันช่วยเหมือนข้อที่แล้ว แต่คราวนี้ไม่ได้ใช้นับ แต่ใช้เก็บลิสต์ที่เรียงใหม่ โดย recursive จับสมาชิกตัวแรก ไปเก็บในอีกลิสต์ต่อๆจากหลังมาหน้าแทนเมื่อ ลิสต์แรกว่าง ลิสต์อีกลิสต์ก็จะเป็นคำตอบคือเป็นลิสต์ใหม่ที่เรียกกลับด้านกับลิสต์อีกอันตอนเริ่มแรก

Haskell

reverseList::[a]->[a]
reverseList xs = reverseList' xs []
                         where
                                 reverseList' [] ys = ys
                                 reverseList' (x:xs) ys = reverseList' xs (x:ys)

Erlang

-module (lninenine).
-export ([reverseList/1]).

reverseList (L) -> reverseList(L,[]).
reverseList ([],R) -> R;
reverseList ([H|T],R) -> reverseList(T,[H|R]).

Lisp

(defun reverse-list-acc (L R)
        (if L
            (reverse-list-acc (rest L) (cons (first L) R))
            R
        )
)

(defun reverse-list (L)
        (reverse-list-acc L nil)
)
28
ธ.ค.
09

แก้โจทย์ L-99:Ninety-Nine Lisp Problems P01

ไปเจอมาจาก blog ของพี่ pok เป็นรวมโจทย์ไว้ฝึกเขียน Lisp แต่ว่าจะเอามาลองเขียนด้วย Haskell,Lisp,Erlang เอาแค่นี้ก่อน

ข้อแรกบอกว่า

P01 (*) Find the last box of a list.
Example:
* (my-last ‘(a b c d))
(D)

หาข้อมูลตัวสุดท้ายของ List ที่เห็นตัวอย่างเป็น D ตัวใหญ่เพราะ ‘(a b c d) lisp มองเป็น list ของ symbol ไม่ใช่ character ซึ่ง symbol เป็น case-insensitive

เริ่มด้วย Haskell ถนัดสุดใน 3 ภาษานี้ก่อน

myLast::[a]->a
myLast (x:[]) = x
myLast (_:xs) = myLast xs

เริ่มจาก กำหนด ประเภท ของฟังก์ชัน ว่าเป็นฟังก์ชันที่รับลิสต์ a ใดๆ แล้วให้ผลลัพธ์เป็นข้อมูลประเภท a แล้วก็นิยามฟังก์ชันว่า ถ้ารับ (x:[]) ถือรับลิสต์ที่มีสมาชิก 1 ตัว ก็ให้ส่งค่านั้นเป็นผลลัพธ์ อีกนิยามก็คือ ถ้ารับ (x:xs) ก็จะทำการเรียกตัวเองอีกรอบโดยส่ง xs ไปเป็นอินพุต นั่นคือ ตัดข้อมูลตัวแรกออก ก็จะวนแบบนี้ไปเรื่อยๆจนไปเข้ารูปแบบของนิยามอันแรกก็จะส่งตัวสุดท้ายของ List ออกมา

Lisp

(defun my-last (L)
(if  (rest L) (my-last (rest L)) (first L)))

สำหรับ Lisp ใช้ฟังก์ชัน first กับ rest ช่วย คือ first จะให้ค่าสมาชิกตัวแรกของลิสต์ ส่วน rest จะให้ลิสต์ที่เหลือยกเว้นสมาชิกตัวแรก ส่วน if ของ lisp ก็มองเป็น function เหมือนกัน โดยที่รับ parameter 3 ค่า ค่าแรกเป็นเงื่อนไข ค่าสองเป็น ผลลัพธ์เมื่อเป็นจริง ค่าสามผลลัพธ์เมื่อเป็นเท็จ จากฟังก์ชันเราหาว่า rest L เป็น nil หรือไม่ ถ้าไม่ ก็ให้ฟังก์ชันเรียกตัวเองโดย ส่ง สมาชิกที่เหลือยกเว้นตัวแรกไปเป็น parameter ถ้า rest L เป็น nil แสดงว่าเหลือสมาชิกแค่ตัวเดียว เราจะให้ฟังก์ชันส่งค่า first คือสมาชิกตัวนั้นเป็นคำตอบ

สุดท้าย Erlang

-module(lninenine).
-export([mylast/1]).

mylast([H|[]]) -> H;
mylast([_|R]) -> mylast(R).
10
ก.พ.
09

Tail Recursion

การทำงานของโปรแกรมโดยทั่วไปเวลาเรียก function นั้นจะมีการจำตำแหน่งที่เรียกเอาไว้แล้วกระโดดเข้าไปทำงานใน function เมื่อเจอคำสั่ง return ก็จะกระโดดกลับมา ดั้งนั้นถ้ามีการเขียนแบบ recursive ก็จะมีการสร้าง stack ของการ call function ซ้อนๆกันไว้ แล้วพอ return ก็จะย้อนกลับมาทีละ step นี่คือกรณีของ recursive แบบธรรมดาทั่วๆไป ซึ่งจะเห็นว่าจะต้องเสียเวลาในการกระโดดกลับมา

Tail Recusion นั้นจะช่วยลดการทำงานตรงนั้นได้โดยแทนที่จะรอให้ได้ผลลัพธ์เมื่อมีการย้อน กลับ ก็จะทำการเก็บผลลัพธ์ตั้งแต่การเรียก recursive function จนเมื่อถึง การ call ครั้งสุดท้ายก็จะเป็นการ return ผลลัพธ์ออกมาทันที ไม่ต้องย้อนกลับไปอีก

ตัวอย่าง ฟังก์ชัน หาความยาวของ list ถ้าเขียนแบบ recursive ธรรมดา ได้แบบนี้

mylength :: [a] -> Int

mylength [] = 0
mylength (y:ys) =  1+mylength (ys)

จะเห็นว่าแบบนี้ terminate function จะรับค่า empty list แล้ว return 0 ออกมา เมื่อมีการ recursive ก็จะเอา 1 ไปบวกไป แบบนี้จะเกิดการ call ไปจนสุด แล้วค่อยเอาค่า มาบวกกันทีหลังแบบนี้

mylength "abc" -> 1+mylength("bc")
                        -> 1+1+mylength("c")
                        -> 1+1+1+mylength("")
                        -> 1+1+1+0
                        -> 1+1+1
                        -> 1+2
                        -> 3

แต่ถ้าเขียนแบบ tail recursive เราจะเพิ่มตัว accumulator เข้ามา ตัว accumulator ก็คือ พารามิเตอร์ที่เก็บ ผลลัพธ์ในแต่ละ step ที่ทำการ recursive เมื่อ terminate ที่เป็นการ call ครั้งสุดท้ายเราจะ return ค่า accumulator ออกมาทันที

mylength :: [a] -> Int
mylength ys =  _mylength ys 0
_mylength [] n = n
_mylength (y:ys) n = _mylength ys (n+1)

ตัวอย่างนี้เราเขียน function _mylenth ขี้นมาเป็น tail recursion แล้วตัวfunction mylength ของเรา ก็ค่อย call _mylength โดยส่งค่า 0 เป็นค่าเริ่มต้นของ accumulator

27
ม.ค.
09

Tree In Haskell

ตอนนี้กำลัง ค่อยๆ ไล่อ่าน หนังสือ Real World Haskell ที่ร่วมกันเขียนโดย  Bryan O’Sullivan, Don Stewart, and John Goerzen
หนังสือตีพิมพ์เป็นเล่มขายแล้ว อยากซื้อเก็บเหมือนกัน แต่ก็ไม่เคยซื้อผ่าน amazon ไม่มีพวกบัตรเครติด อะไรเลย ก็เลยยังไม่ซื้อ

หนังสือเล่มนี้ มีให้อ่านออนไลน์ผ่านเว็บ http://book.realworldhaskell.org/ ที่จริง หนังสือเล่มนี้ก่อนตีพิมพ์ ผู้แต่งเขาก็เอาขึ้นเว็บ
ให้อ่าน และก็ให้ comment ในแต่ละ paragraph ได้ในระหว่างแต่ง เพราะฉนั้นถ้าเข้าไปอ่านจะเห็นว่าในแต่ละ paragraph จะมีลิ้ง
ให้ comment ได้

มาว่ากันตามหัวข้อ คือ เขียนโครงสร้างข้อมูลแบบ Tree ด้วย Haskell ซึ่งมันเป็นแบบฝึกหัดอยู่ที่บทที่ 3 ว่าให้สร้าง data type Tree
โดยให้มี variable constructor ตัวเดียว โดยใช้ data type Maybe a เข้าช่วย นั่งทำอยู่นาน กว่าจะทำได้ แล้วก็ได้ออกมาแบบนี้

data Tree  a = Node a (Maybe (Tree a)) (Maybe (Tree a))
                deriving (Show)

ถ้าแบบไม่ใช้ Maybe ตามตัวอย่างในหนังสือจะเป็นแบบนี้ ซึ่งจะมี variable constructor 2 ตัวโดย มี Empty อีกตัว

data Tree  a = Node a (Tree a) (Tree a) 
                      | Empty
                deriving (Show)

data type Tree ที่สร้างมาเป็น type แบบ Recursive types จะเห็นว่า pattern ของ variable constructor จะมี
data type Tree อยู่ด้วย ตัวอย่างการเอาไปใช้งานแบบ ไม่ใช้ Maybe จะเป็นแบบนี้

myTree = Node 10 Empty Empty
myTree2 = Node 10 (Node 20 Empty Empty) Empty

ส่วนแบบ Maybe เราไม่จำเป็นต้อง สร้าง Empty ขึ้นมาเพราะเราจะใช้ Nothing ซึ่งเป็น ข้อมูลแบบ Maybe ในการกำหนดค่า
childNode ของ Tree ได้ เช่น

myTree = Node 10 Nothing Nothing

และ ใช้ Just ในการกำหนด childNode ที่ไม่เป็น Nothing

myTree2 = Node 10 (Just (Node 20 Nothing Nothing)) Nothing

จบแค่นี้ครับ ไม่ได้อัพบล็อคตัวเองซะนาน เพราะหัวข้ออื่นๆก็เอาไปอัพที่ *66.com ซะหมดแล้ว