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

1 Response to “แก้โจทย์ L-99:Ninety-Nine Lisp Problems P13”


  1. พฤศจิกายน 25, 2016 ที่ 8:43 am

    Dear IPorsut,
    I have these two question following toask how to solve in Erlang language:

    I. (first problem)
    Process pool
    In this exercise we are going to implement a new version of the demonstrated parallel map function: parmapn/3
    It takes an integer ( N) as the first argument to represent the number of worker processes to start, a list of elements ( List) and a function (F )to apply on the elements of the list. We should define two function: one to represent the worker process and one for the supervisor / manager.
    pmap:worker/0
    Define a function worker/0 that repeatedly receives elements from the supervisor, performs the given operation F, and send back the result to the supervisor.

    pmap:parmapn/3
    Define a function parmapn/3that:
    • start a dispatcher process and a collector process
    • starts as many worker processes as the input argument N
    • waits for the results from the collector process

    pmap:dispatcher/0
    Define a function dispatcher/1 that repeatedly sends the elements of the input list to the worker processes. Sending the elements of the lists should not overload the processes. So send an element to a process and only send the next element when it finished the computation on the former element (the worker may notify the dispatcher that it finished the computation).

    pmap:collector/0
    Define a function collector/0 that repeatedly receives elements from the worker processes and sends it to the supervisor in the order of the original list:

    There are some points where we do not restrict the implementation. You may modify the arguments of the non interface function (the only interface is pmap:parmapn/3). So you can decide whether you initialize the processes with some input arguments or send them as messages.

    To test your implementation you may use the pmap_ord function defined on the lab:
    seventh:par_map(fun mapdc:fib/1, [37,36,35]) == pmap:parmapn(12, fun mapdc:fib/1, [37,36,35])

    II (second problem)

    process ring
    In this exercise we are going to implement a process ring where each process has a preceding and a successor process. A message received from the preceding process is sent forward to the successor process, and each process does a little work. This scheme is also called pipeline.
    ring:pipe/1
    Define a function pipe/1 that takes the process identifier of the successor process as argument, and receives messages. Messages have two forms. Either {forward, N} where Nis an integer or quit. In the former case the function increases N by one and sends it forward to the next process and keeps waiting for further messages. In the latter case the function simply forwards the message to the next process and returns.
    ring:start/0
    Define a function start/0 that creates a ring of six processes, like P→A→B→C→D→E→P, where A sends the received message to B, P is the current process.
    The function returns an anonymous function that takes one argument. If the argument is quit the function simply forwards it to process A, and returns a received message. Otherwise it sends the argument as a forward message and returns the received integer.
    For instance:
    1> F = ring:start().
    #Fun
    2> F(1).
    6
    2> F(5).
    10
    3> F(quit).
    quit
    4> F(1).

    Thanks so much


ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s


%d bloggers like this: