Posts Tagged ‘lisp

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)))
                )
        )
)
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 ที่เหลือ

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