99 problems in OCaml🐪 1

working with lists

 

1. 리스트 마지막 원소

let rec last = function
    |[] -> None
    |[x] -> Some x
    |h::t -> last t

2. 마지막 2개 원소

let rec last_two = function
    |[] |[_] -> None
    |[a; b] -> Some (a,b)
    |h::t -> last_two t

3. 리스트 n번째 원소

let rec at n = function
    |[] -> None
    |h::t -> if n>1 then at (n-1) t else Some h

4. 리스트 길이

let rec length = function
    |[] -> 0
    |h::t -> 1 + length t    

(*tail recursive*)
let length lst = 
    let rec aux acc = function
        |[] -> acc
        |h::t -> aux (acc+1) t
    in aux 0 lst

5. 리스트 뒤집기

let rec rev = function
    |[] -> []
    |h::t -> (rev t)@[h]

(*tail recursive*)
let rev lst =
    let rec aux res = function
        |[] -> res
        |h::t -> aux (h::res) t
    in aux [] lst

6. 리스트가 palindrome인지 판단하기

let is_palindrome l = l = List.rev l

(*List.rev 직접구현*)
let is_palindrome l =
    let rec rev acc = function
        |[] -> acc
        |h::t -> rev (h::acc) t
    in l = rev [] l

7. flatten

(* flatten [One "a"; Many [One "b"; Many [One "c" ;One "d"]; One "e"]];; *)
type 'a node =
    | One of 'a 
    | Many of 'a node list;;

let rec flatten = function
    |[] -> []
    |One x :: t -> x::(flatten t)
    |Many l :: t -> (flatten l) @ (flatten t)

(*tail recursive*)
let flatten lst = 
    let rec aux acc = function
        |[] -> acc
        |One x :: t -> aux (x::acc) t
        |Many l :: t -> aux (aux acc l) t    
    in List.rev (aux [] lst)

8. compress

(*
# compress ["a"; "a"; "a"; "a"; "b"; "c"; "c"; "a"; "a"; "d"; "e"; "e"; "e"; "e"];;
- : string list = ["a"; "b"; "c"; "a"; "d"; "e"]
*)    
let rec compress = function
    |[] | [_] as t -> t
    |h1::(h2::_ as t) -> if h1=h2 then compress t else h1::(compress t)

(*tail recursive*)
let compress lst = 
    let rec aux acc = function
        |[] -> acc
        |[x] -> x::acc
        |h1::(h2::_ as t) -> if h1=h2 then aux acc t else aux (h1::acc) t
    in List.rev (aux [] lst)

9. pack

(*
# compress ["a"; "a"; "a"; "a"; "b"; "c"; "c"; "a"; "a"; "d"; "e"; "e"; "e"; "e"];;
- : string list = ["a"; "b"; "c"; "a"; "d"; "e"]
*)

let pack lst = 
    let rec aux l1 l2 = function
        |[] -> []         (* lst가 []이었을 경우만 이 case에 매칭됨 *)
        |[x] -> (x::l1)::l2
        |h1::(h2::_ as t) -> if h1=h2 then aux (h1::l1) l2 t else aux [] ((h1::l1)::l2) t
    in List.rev (aux [] [] lst)

10. RLE (run length encoding)

(*
# encode ["a"; "a"; "a"; "a"; "b"; "c"; "c"; "a"; "a"; "d"; "e"; "e"; "e"; "e"];;
- : (int * string) list =
[(4, "a"); (1, "b"); (2, "c"); (2, "a"); (1, "d"); (4, "e")]
*)

let encode lst =
    let rec aux n acc = function
        |[] -> []              (* lst가 []이었을 경우만 이 case에 매칭됨 *)
        |[x] -> (n+1, x) :: acc
        |h1::(h2::_ as t) -> if h1=h2 then aux (n+1) acc t else aux 0 ((n+1, h1) :: acc) t
    in List.rev (aux 0 [] lst)    

(* 9번 pack 함수 이용하는 버전 *)
let encode lst = 
    List.map (fun l -> List.length l, List.hd l) (pack lst)

11. modified rle. 정의한 rle 타입 적용하는 버전

(*
encode ["a"; "a"; "a"; "a"; "b"; "c"; "c"; "a"; "a"; "d"; "e"; "e"; "e"; "e"];;
- : string rle list =
[Many (4, "a"); One "b"; Many (2, "c"); Many (2, "a"); One "d";
 Many (4, "e")]
 *)

type 'a rle =
    | One of 'a
    | Many of int * 'a;;

let encode lst = 
    let f l = 
        let len = List.length l in 
        if len=1 then One (List.hd l)
        else Many (len, List.hd l)  
    in List.map f (pack lst)

12. rle decode

(*
# decode [Many (4, "a"); One "b"; Many (2, "c"); Many (2, "a"); One "d"; Many (4, "e")];;
- : string list =
["a"; "a"; "a"; "a"; "b"; "c"; "c"; "a"; "a"; "d"; "e"; "e"; "e"; "e"]
*)

(* 풀이 1*)
let decode = function
    | [] -> []
    | Many (n,x) :: t -> if n > 1 then x :: decode (Many (n-1,x) :: t) else x :: decode t
    | One x :: t-> x :: decode t

(* 풀이 2*)
let decode lst =
    let rec len n x = if n=0 then [] else x :: len (n-1) x in
    let rec aux el=
        match el with
        | One x -> [x]
        | Many (n,x) -> len n x 
    in List.flatten (List.map aux lst)

13. encode

let encode lst =
    let rle count x = if count = 1 then One x else Many (count, x) in   (* count와 원소를 받아 rle 타입으로 리턴*)
    let rec aux count list = 
        match list with
        |[] -> []
        |[x] -> [rle (count+1) x]
        |h1::(h2::_ as t) -> if h1=h2 then aux (count+1) t else rle (count+1) h1 :: aux 0 t
    in aux 0 lst

14. 리스트 원소 중복한 리스트 만들기

let rec duplicate = function   
    |[] -> []
    |h::t -> h::h::(duplicate t)

15. 리스트 원소 n번 반복하는 리스트 만들기

(*
# replicate ["a"; "b"; "c"] 3;;
- : string list = ["a"; "a"; "a"; "b"; "b"; "b"; "c"; "c"; "c"]
*)

let rec replicate lst n = 
    let rec aux l m acc =
        match l with
        |[]->acc
        |h::t as l-> if m=1 then aux t n (h::acc) else aux l (m-1) (h::acc)
    in List.rev (aux lst n [])

16. n번째 원소 삭제하기

let rec drop lst n = 
    match lst with
    |[] -> []
    | h::t -> if n=1 then t else h :: drop t (n-1)

17. 리스트 2개로 나누기. 나눠야할 첫번째 리스트 길이 주어짐

let split lst n = 
    let rec aux l m acc = 
        match l with
        |[] -> List.rev acc,[]
        |h::t as l-> if m=0 then List.rev acc, l else aux t (m-1) (h::acc)
    in aux lst n []

18. 리스트에서 a번째부터 b번째까지로 자른 리스트 반환하기

(* 내 풀이 - 17번의 split 함수 활용, aux는 list에서 앞의 n개 원소까지 자르기 *)
let slice list a b = 
    let rec aux l n = 
        match l with 
        |h::t as l-> if n=0 then l else aux t (n-1)
        |[] -> [] 
    in fst (split (aux list a) b-a+1)
    
(* 다른 사람 풀이1 *)
let slice lst a b =
    (* 앞에서 n개 원소 자른 것 리턴 *)
    let rec drop n = function
        |[]->[]
        |h::t as l-> if n=0 then l else drop (n-1) t
    in
    (* 앞에서 n개 원소까지 리턴 *)
    let rec take n acc = function
        |[] -> []
        |h::t-> if n=0 then List.rev acc else take (n-1) (h::acc) t   
    in take (b-a+1) [] (drop a lst)   

(* 다른 사람 풀이2 *)
(* (n번째 원소 까지만 f를 적용한 fold 결과물, 뒷부분 리스트)의 튜플을 리턴하는 함수 *)
let rec fold_until f acc n = function
    |[] -> acc,[]
    |h::t as l-> if n=0 then acc,l else fold_until f (f h acc) (n-1) t 

let slice list a b = 
    (* 앞 부분은 뭐가 되든 상관 없기 때문에 그냥 빈 배열 리턴하는 함수 f로 정의 *)
    let _, rest = fold_until (fun _ _ -> []) [] a list in
    let taken, _ = fold_until (fun h acc -> h::acc) [] (b-a+1) rest in
    List.rev taken

 

19. 리스트를 왼쪽으로 n번 rotate 하기

(*
# rotate ["a"; "b"; "c"; "d"; "e"; "f"; "g"; "h"] 3;;
- : string list = ["d"; "e"; "f"; "g"; "h"; "a"; "b"; "c"]
# rotate ["a"; "b"; "c"; "d"; "e"; "f"; "g"; "h"] (-2);;
- : string list = ["g"; "h"; "a"; "b"; "c"; "d"; "e"; "f"]
*)

let rotate list n = 
    let len = List.length list in
    let n = if n = 0 then 0 else (n mod len + len) mod len in
    let rec aux n = function
        |[] -> []
        |h::t as l-> if n=0 then l else aux (n-1) (t@[h]) 
    in aux pn list

20. n번째 원소 삭제하기. (0부터 인덱싱)

let rec remove_at n = function
    |[] -> []
    |h::t -> if n=0 then t else h :: remove_at (n-1) t

21. 주어진 원소 n번째 위치에 집어넣기

let rec insert_at x n = function
    |[] -> [x]
    |h::t as l-> if n = 0 then x::l else h :: insert_at x (n-1) t

22. a 부터 b까지 순차적으로 1씩 증가하는 (혹은 감소하는) 리스트 리턴

let range a b = 
    let rec aux a b acc = if a>b then List.rev acc else aux (a+1) b (a::acc) in
    if a<b then aux a b [] else List.rev (aux b a [])

23. 리스트에서 n개 원소 랜덤으로 고르기. Random 모듈의 Random.int 함수 이용! 

let random_select list n =
    (* (리스트에서 n번째 원소, 나머지 리스트) 이렇게 튜플로 리턴 *)
    let rec extract nth acc = function
        |[] -> raise (Failure "no element to extract!")
        |h::t -> if nth = 0 then h, acc @ t else extract (nth -1) (h::acc) t in 
    (* n번 동안 acc에 랜덤원소 모으기 *)    
    let rec aux acc n list = 
        if n=0 then acc 
        else 
        let x, rest = extract (Random.int (List.length list)) [] list in aux (x::acc) (n-1) rest
    in let len = List.length list  
    in aux [] (min n len) list

24. 1..m 사이의 숫자 n개 고른 리스트

let lotto_select n m = random_select (range 1 m) n

25. random permutation

let permutation list = random_select list (List.length list)

26. 모든 n개 조합

(*
# extract 2 ["a"; "b"; "c"; "d"];;
- : string list list =
[["a"; "b"]; ["a"; "c"]; ["a"; "d"]; ["b"; "c"]; ["b"; "d"]; ["c"; "d"]]
*)

let rec extract n list = 
    if n <= 0 then [[]]
    else match list with
    |[] -> []
    |h::t -> let with_h = List.map ( fun l-> h::l ) ( extract (n-1) t ) in 
             let without_h = extract n t in 
             with_h @ without_h

27. 리스트 원소 disjoint subset으로 그루핑 하는 모든 조합

(* 예시
# group ["a"; "b"; "c"; "d"] [2; 1];;
- : string list list list =
[[["a"; "b"]; ["c"]]; [["a"; "c"]; ["b"]]; [["b"; "c"]; ["a"]];
 [["a"; "b"]; ["d"]]; [["a"; "c"]; ["d"]]; [["b"; "c"]; ["d"]];
 [["a"; "d"]; ["b"]]; [["b"; "d"]; ["a"]]; [["a"; "d"]; ["c"]];
 [["b"; "d"]; ["c"]]; [["c"; "d"]; ["a"]]; [["c"; "d"]; ["b"]]]
 *)
 
 (* 내 풀이 *)
 (* 26번 extract 변형 (n개 뽑은 것, 나머지) 튜플 리스트로 리턴 *)
let rec extract n list = 
    if n<=0 then [[],list]
    else match list with
    |[] -> []
    |h::t -> let with_h = List.map (fun (x,y) -> h::x,y ) (extract (n-1) t) in
             let without_h = List.map (fun (x,y) -> x,h::y) (extract n t) in
             with_h @ without_h

let rec group list = function
    |[] -> [[]]
    |h::t -> let h_list = extract h list in
             let result = List.map (fun (h_extracted,rest) -> List.map (fun l -> h_extracted::l) (group rest t)) h_list in 
             List.flatten result

 

 

(* 사이트 풀이 *)
(* This implementation is less streamlined than the one-extraction
    version, because more work is done on the lists after each
    transform to prepend the actual items. The end result is cleaner
    in terms of code, though. *)
  
let group list sizes =
    let initial = List.map (fun size -> size, []) sizes in

(* The core of the function. Prepend accepts a list of groups,
    each with the number of items that should be added, and
    prepends the item to every group that can support it, thus
    turning [1,a ; 2,b ; 0,c] into [ [0,x::a ; 2,b ; 0,c ];
    [1,a ; 1,x::b ; 0,c]; [ 1,a ; 2,b ; 0,c ]]

    Again, in the prolog language (for which these questions are
    originally intended), this function is a whole lot simpler.  *)
    let prepend p list =
      let emit l acc = l :: acc in
      let rec aux emit acc = function
        | [] -> emit [] acc
        | (n, l) as h :: t ->
           let acc = if n > 0 then emit ((n - 1, p :: l) :: t) acc
                     else acc in
           aux (fun l acc -> emit (h :: l) acc) acc t
      in
      aux emit [] list
    in
    let rec aux = function
      | [] -> [initial]
      | h :: t -> List.concat (List.map (prepend h) (aux t))
    in
    let all = aux list in
    (* Don't forget to eliminate all group sets that have non-full
       groups *)
    let complete = List.filter (List.for_all (fun (x, _) -> x = 0)) all in
      List.map (List.map snd) complete;;

prepend  => 원소가 어떤 각 set에 들어가는 ( 해당 set에 들어갈 수 있는 경우만.) + 아무 set에도 안들어가는 모든 경우의 수에 대한 리스트 리턴.

emit => acc 에 새로운 경우의 수 포함하기.

재귀함수 call 마다 emit 함수 재정의 하는데, 그 경우의 수가 지금 head도 포함하도록 하기 위해서 이다.

 ( (1,a) :: [(2,b), (3,c)] ) :: acc 

      ⬆️          ⬆️

  지금 h     다음 h