make it functional 함수형 프로그래밍의 모든 것

역시 하스켈을 이용합니다. 일단 스킴과 달리 하스켈은 중첩 리스트를 언어 자체에서 지원하지 않습니다. 왜냐하면 리스트의 원소는 모두 똑같은 자료형이어야 하는 데 수와 리스트는 자료형이 서로 다르기 때문이지요. 그래서 일단 자료형부터 만듭니다.

data Nested a = Item a | Nest [Nested a] deriving (Eq, Show)

수는 Item, 리스트는 Nest 생성자를 붙여서 똑같이 Nested 형으로 만들어줍니다. 이제 예를 들어 [1,[2,3]]은 Nest [Item 1, Nest [Item 2, Item 3]]이 됩니다. 입력하기가 번거로우면 에디터에서 찾아바꾸기로 [는 모두 Nest [로 바꿔주고 수 앞에 Item을 붙여주세요.

이제 꼬리 재귀 버전으로 만들어보겠습니다. 맨 앞에서부터 수를 하나씩 꺼내고 나머지는 꼬리 재귀를 하면 됩니다.

리스트의 가능한 조합은 빈 리스트, 수:리스트와 리스트:리스트 세 가지 입니다. 이 중에 리스트:리스트는 다시 빈 리스트:리스트와 비지 않은 리스트:리스트 두 가지가 있습니다. 따라서 모두 네 종류의 조합이 있고 각각에 대해 패턴 매칭을 해주면 됩니다. 먼저 빈 리스트일 경우에는 간단합니다.

flatten (Nest []) = []

그 다음으로 수:리스트인 경우도 간단합니다.

flatten (Nest ((Item x):xs)) = x:flatten (Nest xs)

빈 리스트 : 리스트인 경우에는 앞에 빈 리스트를 무시하면 되겠습니다.

flatten (Nest (Nest []:xs)) = flatten $ Nest xs

끝으로 비지 않은 리스트:리스트인 경우는 수:리스트 꼴로 바꿔줍니다. 예를 들어 [[1,2],3] 이런 경우에는 [1,[2],3]으로 바꿉니다. 그러면 수:리스트가 됩니다.

flatten (Nest ((Nest (x:xs)):xss)) = flatten $ Nest (x:Nest xs:xss)

문제에 있는 코드로 테스트를 해보겠습니다.

> flatten (Nest [Item 1, Item 2, Nest [Item 3, Item 4, Nest [Item 5]], Item 6, Nest [Nest [Item 7,Item 8]]])
[1,2,3,4,5,6,7,8]

하스켈은 기본적으로 지연평가(lazy evaluation)을 하기 때문에 x:xs라고 되어 있으면 x만 처리하고 xs는 처리하지 않습니다. 그래서 x:flatten (Nest xs)에서 x:를 평가하고 그 다음에 flatten (Nest xs)를 평가하여 꼬리 재귀가 됩니다.

스킴으로 똑같이 짜면 아래와 같습니다.

(define (flatten lst)
  (cond
    ((null? lst) lst)
    ((not (list? (car lst))) (cons (car lst) (flatten (cdr lst))))
    ((null? (car lst)) (flatten (cdr lst)))
    (else (flatten (cons (caar lst) (cons (cdar lst) (cdr lst)))))))

스킴은 즉시 평가(eager evaluation)을 하기 때문에 (cons (car lst) (flatten (cdr lst)))를 하려면 flatten이 cons보다 먼저 실행되서 꼬리 재귀가 안됩니다. 스킴에서 꼬리 재귀가 되게 하려면 delay와 force를 이용하여 지연 평가를 하도록 코드를 수정해야 합니다.

더 간단합니다만 더 효율적이진 않습니다.

data Nested a = Item a | Nest [Nested a] deriving (Show, Eq)

flatten (Item x) = [x]
flatten (Nest xs) = concatMap flatten xs

알고리즘은 똑같은 같아요. tail-recursion 은 아니구요.

type nested = Item of int| Nest of nested list

let temp = [Item 1; Item 2; Nest [Item 3; Item 4; Nest [Item 5]]; Item 6; Nest[Nest[Item 7;Item 8]]]

(* test : nested list -> int list *)
let rec flatten nl =
  match nl with
      [] -> []
    | x::xs -> (
          match x with
              Item y -> [y]@(flatten xs)
            | Nest ys -> (flatten ys)@(flatten xs))

결과

# flatten temp;;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8]

I wanna know you~!

(define (flat x)
  (cond ((null? x) '())
        ((not (pair? x)) (list x))        
        (else (append (flat (car x)) (flat (cdr x))))))