Archive Page 2

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
        )
)
Advertisements
04
ม.ค.
10

เอิร์ลแลง(Erlang) concurrent programming ตอน 2 ส่ง Message

คราวที่แล้วเราสร้าง process ด้วย spawn ไปแล้ว คราวนี้เราจะมาดูวิธี ส่ง และ รับ message ระหว่าง processes

การเขียนฟังก์ชันให้รอรับ message นั้นใช้คีย์เวิร์ด receive …. end. ตัวอย่างเช่น

-module(chat).
-export([alert/0]).

alert () ->
        receive
                Any ->
                        io:format("Alert : ~w~n",[Any])
        end.

ตรงระหว่าง receive กับ end นั้นจะเป็น pattern ของ message และ action เมื่อเจอ message pattern นั้นส่งมาหา process ที่กำลังทำงานฟังก์ชันนี้อยู่

ทีนี้ วิธีการส่ง message ไปหา process จะใช้รูปแบบนี้

Eshell V5.7.2  (abort with ^G)
1> c(chat).
{ok,chat}
2> PID = spawn(chat,alert,[]).
<0.42.0>
3> PID ! hello.
Alert Hello: hello
hello
4> halt().

โดยที่ทางซ้ายคือ PID (process id) ส่วนทางขวา จะเป็น message ที่ต้องการส่ง

receive end. จะรอรับ message แต่ครั้งเดียว เมื่อมี message ส่งมาแล้วก็จะหยุด แต่ถ้าเราต้องการให้ process รอรับ message อีกรอบ ก็ให้เรียกซ้ำฟังก์ชันอีกครั้งแบบนี้

-module(chat).
-export([alert/0]).

alert () ->
        receive
                Any ->
                        io:format("Alert : ~w~n",[Any])
        end,
        alert().
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)))
                )
        )
)
03
ม.ค.
10

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

ขอข้ามข้อ P06 ไปนะครับ มาที่ข้อ P07

P07 (**) Flatten a nested list structure.
Transform a list, possibly holding lists as elements into a `flat’ list by replacing each list with its elements (recursively).

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

ข้อนี้คือสร้างฟังก์ชัน my-flatten ที่รับค่าลิสต์ที่ซ้อนๆกันอยู่เข้ามาแล้วทำการทำให้เป็นลิสต์เดียวที่ไม่ซ้อนกันอีก ข้อนี้สำหรับภาษา lisp กับ erlang ไม่มีปัญหาอะไร เพราะลิสต์ของทั้งสองภาษานี้ทำซ้อนๆกันแบบนี้ได้ เพราะไม่จำกัดว่าข้อมูลในลิสต์ต้องเป็นประเภทเดียวกัน แต่ haskell ทำแบบนี้ไม่ได้ ถ้าจะซ้อนก็คือทุกสมาชิกก็ต้องเป็นลิสต์ที่ซ้อนอยู่เหมือนกัน ดังนั้นก็จะทำแค่ erlang กับ lisp

Erlang

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

flatten ([]) -> [];
flatten ([H|T]) when is_list(H) -> lists:append( flatten(H) , flatten(T));
flatten ([H|T]) -> lists:append([H], flatten(T)).

Lisp

(defun flatten (orig-list)
    (if (eql orig-list nil)
        nil
        (let ((elem (car orig-list)) (resto-list (cdr orig-list)))
            (if (listp elem)
                (append (flatten elem) (flatten resto-list))
                (append (cons elem nil) (flatten resto-list))))))

วิธีคิดก็คือ เช็คว่าแต่ละ element ตัวแรกเป็นลิสต์หรือไม่ถ้าใช่เราก็จะเรียกฟังก์ชันอีกครั้งกับ element ตัวนั้น และ เอาผลลัพธ์ที่ได้มา ต่อกัน (append) กับ การเรียกฟังก์ชันซ้ำ กับ element ที่เหลือ ถ้าไม่ใช่ก็เอา element ตัวนั้นไป append กับผลที่ได้จากการเรียกซ้ำฟังก์ชันของ element ที่เหลือ

01
ม.ค.
10

เอิร์ลแลง(Erlang) concurrent programming ตอน 1 Processes

Erlang สามารถเขียนให้โปรแกรมทำหลายๆงานพร้อมกันได้ โดยแต่ละงานที่ทำก็คือ 1 โปรเซส ใน Erlang BIF (built-in function) มีฟังก์ชันชื่อ spawn ที่จะสร้างโปรเซสใหม่ขึ้นมา

spawn(Module, Exported_Function, List of Arguments)

โดย arguments ที่ต้องส่งให้ spawn มี Module  ของฟังก์ชันที่จะเรียก , Exported_Function คือฟังก์ชันที่จะเรียก, ค่าสุดท้ายคือ List ของ Arguments ที่จะส่งให้ฟังก์ชัน spawn ก็จะไปสร้าง โปรเซส ให้ทำงานตามฟังก์ชันที่กำหนดไป และตัวฟังก์ชัน spawn เองก็จะส่งค่า process id กลับมา

ตัวอย่าง

-module(tut14).
-export([start/0, say_something/2]).
say_something(What, 0) ->
    done;
say_something(What, Times) ->
    io:format("~p~n", [What]),
    say_something(What, Times - 1).
start() ->
    spawn(tut14, say_something, [hello, 3]),
    spawn(tut14, say_something, [goodbye, 3]).

เมื่อเรียก start ให้ทำงานผ่าน erl

1>c(tut14).
{ok,tut14}
2>tut14:start().
hello
goodbye
<0.63.0>
hello
goodbye
hello
goodbye

เมื่อเราเรียก start จะเห็นจากโค้ดว่า start จะสร้าง process ใหม่มาอีก 2 ตัวโดยใช้ spawn ตัวแรกให้เรียกฟังก์ชัน say_something โดยส่ง hello กับ 3 ไปเป็น arguments ส่วน ตัวที่สองส่ง goodbye กับ 3 ผลลัพธ์ที่ได้ก็คือ ทั้ง 2 process ก็ต่างไปทำงานตามฟังก์ชัน say_something ที่เขียนไว้ เลยได้ goodbye กับ hello สลับๆกันไปมา จะเห็นว่ามี <0.63.0> ออกมาด้วย ค่านี้มาจากฟังก์ชัน start คือผลลัพธ์ของฟังก์ชันคือค่าสุดท้าย นั่นก็คือ ผลจากการเรียก spawn ตัวที่สอง ค่า <0.63.0> คือ process id ที่ spawn ส่งกลับมานั่นเอง

ตอนต่อไปค่อยมาว่าเรื่องการส่ง message หากัน ระหว่าง processes

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).