前言
This section is inspired by Ninety-Nine Lisp Problems which in turn was based on “Prolog problem list” by Werner Hett.
原来是 Lisp 的问题改过来的，还得是认祖归宗啊。
笔记
1. Write a function last : ‘a list -> ‘a option that returns the last element of a list
判断列表长度，match 长度处理。
let last l=
let len = List.length l in
match len with
| 0 -> Option.none
| _ -> let pos = len-1 in
List.nth_opt l pos;;
val last : 'a list -> 'a option = <fun>
其实可以直接 match list 的，切片递归处理，有点 Scheme 的意思了，OCaml 这个模式匹配还比 Scheme 的 car 和 cdr 更灵活。
# let rec last = function
| [] -> None
| [ x ] -> Some x
| _ :: t -> last t;;
val last : 'a list -> 'a option = <fun>
2. Find the last but one (last and penultimate) elements of a list.
我猜测可能有什么语法糖。
# let rec last_two = function
| [] -> None
| a::[] -> None
| a::b::[] -> Some (a,b)
| _ :: t -> last t;;
val last_two : 'a list -> ('a * 'a) option = <fun>
# let rec last_two = function
| [] | [_] -> None
| [x; y] -> Some (x,y)
| _ :: t -> last_two t;;
val last_two : 'a list -> ('a * 'a) option = <fun>
3. N’th Element of a List
Find the N’th element of a list.
啥意思，给了库函数了都，用递归改写一下吗？
let rec at k = function
| [] -> None
| h :: t -> if k = 0 then Some h else at (k - 1) t;;
val at : int -> 'a list -> 'a option = <fun>
4. Length of a List
Find the number of elements of a list.
这是 continuation 啊，来了来了。
let rec length = function
| [] -> 0
| _ :: t -> let remain = length t in 1 + remain;;
val length : 'a list -> int = <fun>
哦？也行。
# let length list =
let rec aux n = function
| [] -> n
| _ :: t -> aux (n + 1) t
in
aux 0 list;;
val length : 'a list -> int = <fun>
5. Reverse a list.
直接用 append 了，我感觉应该有别的好办法，在 OCaml 里怎么切片呢？或者 match 还有什么语法糖？
let rec rev = function
| [] -> []
| [a] -> [a]
| h :: t -> let res = rev t in List.append res [h];;
val rev : 'a list -> 'a list = <fun>
哦，弱智了。
# let rev list =
let rec aux acc = function
| [] -> acc
| h :: t -> aux (h :: acc) t
in
aux [] list;;
val rev : 'a list -> 'a list = <fun>
6. Palindrome
Find out whether a list is a palindrome.
OCaml 里怎么比较两个基本类型相等？哦，强啊。是不是有递归做法？我还是不知道怎么切片。
let is_palindrome s =
let pa_s= rev s in
List.equal (=) pa_s s;;
val is_palindrome : 'a list -> bool = <fun>
哎，想多了，原来 list 能直接 = 的。== 好像是比较地址。
# let is_palindrome list =
(* One can use either the rev function from the previous problem, or the built-in List.rev *)
list = List.rev list;;
val is_palindrome : 'a list -> bool = <fun>
7. Flatten a List
Flatten a nested list structure.
type 'a node =
| One of 'a
| Many of 'a node list;;
type 'a node = One of 'a | Many of 'a node list
let rec flatten l = match l with
| [] -> []
| One x :: t -> let res= flatten t in
List.cons x res
| Many list :: t -> let h= flatten list in
let res= flatten t in
List.append h res;;
val flatten : 'a node list -> 'a list = <fun>
标准答案 rev 了一下，为了避免将一个 list 顺序 cons 到另一个上这个操作，也就是 List.append，我查下 a little Scheme 里怎么做的。书里面好像没有。
append 好像也得用 rev 和 cons 一起实现，这个 rev 似乎避免不了。
# type 'a node =
| One of 'a
| Many of 'a node list;;
type 'a node = One of 'a | Many of 'a node list
# (* This function traverses the list, prepending any encountered elements
to an accumulator, which flattens the list in inverse order. It can
then be reversed to obtain the actual flattened list. *);;
# let flatten list =
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 [] list);;
val flatten : 'a node list -> 'a list = <fun>
8. Eliminate Duplicates
Eliminate consecutive duplicates of list elements.
没仔细读题，题意不是去重，而是去连续的重。写成那个 rember 了。
let rec compress l =
match l with
| [] -> []
| h :: t -> if List.exists ((=) h) t then compress t else List.cons h (compress t);;
val compress : 'a list -> 'a list = <fun>
可以可以，还能这么玩，想想在 Scheme 里要处理这种留存上一个元素状态的情况真有点麻烦，只能带着状态传下去用 cond 判断了。
# let rec compress = function
| a :: (b :: _ as t) -> if a = b then compress t else a :: compress t
| smaller -> smaller;;
val compress : 'a list -> 'a list = <fun>
9. Pack Consecutive Duplicates
Pack consecutive duplicates of list elements into sublists.
有一些开始和结束的空列表会被错误的添加入结果中，要是用 if 排除又太过丑陋，我想想能否优化一下。
let pack l=
let rec rec_pack r rune_l remain_l =
match remain_l with
| [] -> [rune_l]
| h::t -> if h = r then let new_rune_l = (List.cons h rune_l) in rec_pack h new_rune_l t
else List.cons rune_l (rec_pack h [h] t) in
rec_pack "" [] l;;
val pack : string list -> string list list = <fun>
按这个思路好像是能用 Option 再简化一下，有点麻烦。
哎，差不多，标准答案又是那个要 rev 一下的。还是多用 :: 少用 List.cons 吧，确实美观一点，入参只是空格分开实在影响可读性。
标准答案的这几个都是将最后的返回作为参数一步步传入，因此都是逆序 cons 到最后结果的列表上的，自然最后需要逆序一下。可以理解。为啥不爱用 continuation 呢。
# let pack list =
let rec aux current acc = function
| [] -> [] (* Can only be reached if original list is empty *)
| [x] -> (x :: current) :: acc
` | a :: (b :: _ as t) ->
if a = b then aux (a :: current) acc t
else aux [] ((a :: current) :: acc) t in
List.rev (aux [] [] list);;
val pack : 'a list -> 'a list list = <fun>
10. Run-Length Encoding
抄第九道搞出来的，有没有更简单的方法呢？
let encode list =
let rec encode_rec num acc = function
| [] -> [] (* Can only be reached if original list is empty *)
| [x] -> (num + 1, x) :: acc
| a :: ((b :: _) as t) ->
if a = b then encode_rec num + 1 acc t
else encode_rec 0 ((num + 1, a):: acc) t in
List.rev (encode_rec 0 [] list);;
把递归向下传递的参数优化了一下，只传当前字符已经重复了的次数即可。
let encode list =
let rec encode_rec num acc = function
| [] -> [] (* Can only be reached if original list is empty *)
| [x] -> (num + 1, x) :: acc
| a :: ((b :: _) as t) ->
if a = b then encode_rec (num + 1) acc t
else encode_rec 0 ((num + 1, a):: acc) t in
List.rev (encode_rec 0 [] list);;
val encode : 'a list -> (int * 'a) list = <fun>
差不多，用 pack 的那个有点意思，用了 List.map 把 pack 的结果 map 过去了，挺好。
# let encode list =
let rec aux count acc = function
| [] -> [] (* Can only be reached if original list is empty *)
| [x] -> (count + 1, x) :: acc
| a :: (b :: _ as t) -> if a = b then aux (count + 1) acc t
else aux 0 ((count + 1, a) :: acc) t in
List.rev (aux 0 [] list);;
val encode : 'a list -> (int * 'a) list = <fun>
(* An alternative solution, which is shorter but requires more memory,
is to use the pack function declared in problem 9: *)
# let pack list =
let rec aux current acc = function
| [] -> [] (* Can only be reached if original list is empty *)
| [x] -> (x :: current) :: acc
| a :: (b :: _ as t) ->
if a = b then aux (a :: current) acc t
else aux [] ((a :: current) :: acc) t in
List.rev (aux [] [] list);;
val pack : 'a list -> 'a list list = <fun>
# let encode list =
List.map (fun l -> (List.length l, List.hd l)) (pack list);;
val encode : 'a list -> (int * 'a) list = <fun>
11. Modified Run-Length Encoding
Modify the result of the previous problem in such a way that if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are transferred as (N E) lists.
又用到了 10 题，感觉还能简化下，一遍遍历完成。
type 'a rle =
| One of 'a
| Many of int * 'a;;
let encode l=
let inner_encode list =
let rec aux count acc = function
| [] -> [] (* Can only be reached if original list is empty *)
| [x] -> (count + 1, x) :: acc
| a :: (b :: _ as t) -> if a = b then aux (count + 1) acc t
else aux 0 ((count + 1, a) :: acc) t in
List.rev (aux 0 [] list) in
List.map (fun e -> (let (x, y)= e in if x >1 then Many (x, y) else One y)) (inner_encode l);;
# type 'a rle =
| One of 'a
| Many of int * 'a;;
type 'a rle = One of 'a | Many of int * 'a
# let encode l =
let create_tuple cnt elem =
if cnt = 1 then One elem
else Many (cnt, elem) in
let rec aux count acc = function
| [] -> []
| [x] -> (create_tuple (count + 1) x) :: acc
| hd :: (snd :: _ as tl) ->
if hd = snd then aux (count + 1) acc tl
else aux 0 ((create_tuple (count + 1) hd) :: acc) tl in
List.rev (aux 0 [] l);;
val encode : 'a list -> 'a rle list = <fun>
12. Decode a Run-Length Encoded List
可以直接 map 再用 List.append reduce 一下，或者 flatten。
或者有几个就 cons 几个，然后 rev。
let rec decode l =
let rec multi_cons e cnt acc=
if cnt >0 then (multi_cons e (cnt-1) (List.cons e acc)) else acc
in
let rec inner_decode l acc=
match l with
| [] -> acc
| h::(t) -> match h with
| One e -> inner_decode t (List.cons e acc)
| Many (cnt, e) -> inner_decode t (List.append (multi_cons e cnt []) acc)
in
List.rev (inner_decode l [])
简化
let decode l =
let rec multi_cons e cnt acc=
if cnt >0 then (multi_cons e (cnt-1) (List.cons e acc)) else acc
in
let match_e e= match e with
| One e -> [e]
| Many (cnt, e) -> multi_cons e cnt []
in
List.flatten (List.map match_e l);;
val decode : 'a rle list -> 'a list list = <fun>
哦，和我第一个思路差不多，先 rev 了 list，因为后面增加元素了，更节约一点。
# let decode list =
let rec many acc n x =
if n = 0 then acc else many (x :: acc) (n - 1) x
in
let rec aux acc = function
| [] -> acc
| One x :: t -> aux (x :: acc) t
| Many (n, x) :: t -> aux (many acc n x) t
in
aux [] (List.rev list);;
val decode : 'a rle list -> 'a list = <fun>
13. Run-Length Encoding of a List (Direct Solution)
Implement the so-called run-length encoding data compression method directly.
按这个意思我已经实现了。
14. Duplicate the Elements of a List
Duplicate the elements of a list.
还就是那个 Continuation。
let rec duplicate l = match l with
| [] -> []
| h::(t) -> List.cons h (List.cons h (duplicate t));;
val duplicate : 'a list -> 'a list = <fun>
哦，又忘了用 ::
# let rec duplicate = function
| [] -> []
| h :: t -> h :: h :: duplicate t;;
val duplicate : 'a list -> 'a list = <fun>
15. Replicate the Elements of a List a Given Number of Times
可以的，还是 Continuation，好！
let rec replicate l cnt =
let rec dup h cnt remain=
if cnt >0 then h::(dup h (cnt-1) remain) else remain
in
match l with
| [] -> []
| h::t -> dup h cnt (replicate t cnt);;
val replicate : 'a list -> int -> 'a list = <fun>
我怎么感觉我的比他的好，标准答案擅长用 rev，读起来有点混乱。
确实，不知道是不是存在递归消耗之类原因导致他选择使用这种方式，他的明显多了一次 rev 的消耗。后面又看到了，原来是我这种写法非尾递归，会爆栈，所以不这么写。
# let replicate list n =
let rec prepend n acc x =
if n = 0 then acc else prepend (n-1) (x :: acc) x in
let rec aux acc = function
| [] -> acc
| h :: t -> aux (prepend n acc h) t in
(* This could also be written as:
List.fold_left (prepend n) [] (List.rev list) *)
aux [] (List.rev list);;
val replicate : 'a list -> int -> 'a list = <fun>
16. Drop Every N’th Element From a List
感觉这个反而很基础啊。
let rec drop l i=match l with
| h::t -> if i > 1 then h::drop t (i-1) else t;;
Lines 1-2, characters 17-48:
Warning 8 [partial-match]: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
[]
val drop : 'a list -> int -> 'a list = <fun>
partial-match 了，意思到了就行。
癌，原来他是 every N’th，后面也要递归的。
为啥特意还搞一个内部函数呢，还把 index 转了一下，神秘。后面又看到了，原来是我这种写法非尾递归，会爆栈，所以不这么写。
# let drop list n =
let rec aux i = function
| [] -> []
| h :: t -> if i = n then aux 1 t else h :: aux (i + 1) t in
aux 1 list;;
val drop : 'a list -> int -> 'a list = <fun>
17. Split a List Into Two Parts; The Length of the First Part Is Given
只能在头加，没法避免这个 rev。
let split l n =
let rec inner_split l n acc= match l with
| [] -> [(List.rev acc); []]
| h::t -> if n > 0 then inner_split t (n-1) (h::acc) else [(List.rev acc); h::t]
in
inner_split l n [];;
val split : 'a list -> int -> 'a list list = <fun>
# let split list n =
let rec aux i acc = function
| [] -> List.rev acc, []
| h :: t as l -> if i = 0 then List.rev acc, l
else aux (i - 1) (h :: acc) t
in
aux n [] list;;
val split : 'a list -> int -> 'a list * 'a list = <fun>
18. Extract a Slice From a List
Given two indices, i and k, the slice is the list containing the elements between the i‘th and k‘th element of the original list (both limits included). Start counting the elements with 0 (this is the way the List module numbers elements).
来了来了。
啥玩意，还是包左包右的，你不太行。
输入不合法的时候会无法预料结果。
let rec slice l start e = match l with
| [] -> []
| h::t -> if start>0 && e>0 then (slice t (start-1) (e-1))
else if e>=0 then h::(slice t (start-1) (e-1))
else [];;
val slice : 'a list -> int -> int -> 'a list = <fun>
也可以，先 drop 了。我想想复杂度。少了几次对于 index 的计算，也行吧，确实节约一点。
# let slice list i k =
let rec take n = function
| [] -> []
| h :: t -> if n = 0 then [] else h :: take (n - 1) t
in
let rec drop n = function
| [] -> []
| h :: t as l -> if n = 0 then l else drop (n - 1) t
in
take (k - i + 1) (drop i list);;
val slice : 'a list -> int -> int -> 'a list = <fun>
这个把 fold 和 taken 又抽象了一下，感觉没必要，taken 给的那个 f 甚至是一个 (fun _ _ -> [])这种抽象不是增加困难吗。
# let rec fold_until f acc n = function
| [] -> (acc, [])
| h :: t as l -> if n = 0 then (acc, l)
else fold_until f (f acc h) (n - 1) t
let slice list i k =
let _, list = fold_until (fun _ _ -> []) [] i list in
let taken, _ = fold_until (fun acc h -> h :: acc) [] (k - i + 1) list in
List.rev taken;;
val fold_until : ('a -> 'b -> 'a) -> 'a -> int -> 'b list -> 'a * 'b list =
<fun>
val slice : 'a list -> int -> int -> 'a list = <fun>
19. Rotate a List N Places to the Left
Rotate a list N places to the left.
癌，偷懒了，终于有切片用了。
let rotate l n= List.append (slice l n (List.length l)) (slice l 0 (n-1));;
val rotate : 'a list -> int -> 'a list = <fun>
啊？这么复杂吗，什么情况，哦，也差不多，他用的是 split。let n = if len = 0 then 0 else (n mod len + len) mod len in什么用处呢？哦，兼容了一下负数。也没要求兼容啊。
# let split list n =
let rec aux i acc = function
| [] -> List.rev acc, []
| h :: t as l -> if i = 0 then List.rev acc, l
else aux (i - 1) (h :: acc) t in
aux n [] list
let rotate list n =
let len = List.length list in
(* Compute a rotation value between 0 and len - 1 *)
let n = if len = 0 then 0 else (n mod len + len) mod len in
if n = 0 then list
else let a, b = split list n in b @ a;;
val split : 'a list -> int -> 'a list * 'a list = <fun>
val rotate : 'a list -> int -> 'a list = <fun>
20. Remove the K’th Element From a List
Remove the K’th element from a list.
The first element of the list is numbered 0, the second 1,…
这下是我第一次实现的 16. 了
let rec remove_at i l=match l with
| h::t -> if i > 1 then h::remove_at (i-1) t else t;;
# let rec remove_at n = function
| [] -> []
| h :: t -> if n = 0 then t else h :: remove_at (n - 1) t;;
val remove_at : int -> 'a list -> 'a list = <fun>
21. Insert an Element at a Given Position Into a List
Start counting list elements with 0. If the position is larger or equal to the length of the list, insert the element at the end. (The behavior is unspecified if the position is negative.)
let rec insert_at e i l= match l with
| [] -> [e]
| h::t -> if i>0 then h::(insert_at e (i-1) t) else e::h::t;;
val insert_at : 'a -> int -> 'a list -> 'a list = <fun>
# 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;;
val insert_at : 'a -> int -> 'a list -> 'a list = <fun>
22. Create a List Containing All Integers Within a Given Range
If first argument is greater than second, produce a list in decreasing order.
又写了个死循环给我浏览器干死机了，哈哈。
let rec range a b=if a<b then
a :: range (a+1) b
else if b<a then
a :: range (a-1) b
else
[a];;
val range : int -> int -> int list = <fun>
感觉没我智力高，通过变参数的位置，还是正向 range，还要 rev。
# let range a b =
let rec aux a b =
if a > b then [] else a :: aux (a + 1) b
in
if a > b then List.rev (aux b a) else aux a b;;
val range : int -> int -> int list = <fun>
哦。
A tail recursive implementation:
# let range a b =
let rec aux acc high low =
if high >= low then
aux (high :: acc) (high - 1) low
else acc
in
if a < b then aux [] b a else List.rev (aux [] a b);;
val range : int -> int -> int list = <fun>
23. Extract a Given Number of Randomly Selected Elements From a List
The selected items shall be returned in a list. We use the Random module but and initialise it with Random.init 0 at the start of the function for reproducibility and validate the solution. To make the function truly random, however, one should remove the call to Random.init 0
随机取几个元素？哦，查了下，OCaml 这个随机模块是那种能用种子初始化的伪随机。
这种 partial-match 该怎么处理？我无法提前得知列表的类型，所以无法为这种情况设置一个默认返回值什么的。
let rand_select l count=
let rec remove_at i l=match l with
| h::t -> if i > 0 then
let (e, remain)= (remove_at (i-1) t) in (e, (h::remain)) else (h, t)
in
let rec inner_rand_select list count acc = if count=0 then acc else
let (e, remain) = remove_at (Random.int (List.length list)) list in
inner_rand_select remain (count-1) (e::acc) in
inner_rand_select l count [];;
Lines 2-4, characters 23-71:
Warning 8 [partial-match]: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
[]
val rand_select : 'a list -> int -> 'a list = <fun>
哦，直接抛异常，可以的。
用(min n len)保证了一下输入合法。
# let rand_select list n =
Random.init 0;
let rec extract acc n = function
| [] -> raise Not_found
| h :: t -> if n = 0 then (h, acc @ t) else extract (h :: acc) (n - 1) t
in
let extract_rand list len =
extract [] (Random.int len) list
in
let rec aux n acc list len =
if n = 0 then acc else
let picked, rest = extract_rand list len in
aux (n - 1) (picked :: acc) rest (len - 1)
in
let len = List.length list in
aux (min n len) [] list len;;
val rand_select : 'a list -> int -> 'a list = <fun>
24. Lotto: Draw N Different Random Numbers From the Set 1..M
Draw N different random numbers from the set 1..M.
The selected numbers shall be returned in a list.
组合一下。不过效率太低了，还是得生成后去重。
let lotto_select count max = rand_select (range 0 max) count;;
val lotto_select : int -> int -> int list = <fun>
什么情况，答案也赖皮了。
# (* [range] and [rand_select] defined in problems above *)
let lotto_select n m = rand_select (range 1 m) n;;
val lotto_select : int -> int -> int list = <fun>
25. Generate a Random Permutation of the Elements of a List
Generate a random permutation of the elements of a list.
之前的 rand_select 还有 bug，没法随机到列表的最后一个元素，但只存在一个元素的时候又能随机到了，很神秘啊，顺手改了下。这种带随机的有点难看出来有 bug。
let permutation l = rand_select l ((List.length l));;
val permutation : 'a list -> 'a list = <fun>
也是 rand_select。
# let permutation list =
let rec extract acc n = function
| [] -> raise Not_found
| h :: t -> if n = 0 then (h, acc @ t) else extract (h :: acc) (n - 1) t
in
let extract_rand list len =
extract [] (Random.int len) list
in
let rec aux acc list len =
if len = 0 then acc else
let picked, rest = extract_rand list len in
aux (picked :: acc) rest (len - 1)
in
aux [] list (List.length list);;
val permutation : 'a list -> 'a list = <fun>
27. Generate the Combinations of K Distinct Objects Chosen From the N Elements of a List
Generate the combinations of K distinct objects chosen from the N elements of a list.
In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficients). For pure mathematicians, this result may be great. But we want to really generate all the possibilities in a list.
就是排列组合，传统递归了。
可以 rev 一下的，不过也没要求保留原列表排序。
let extract i l =
let rec inner_extract remain_i acc l= match l with
| [] -> if remain_i = 0 then [acc] else []
| h :: t ->
if (List.length t)+1 < remain_i then []
else if remain_i > 0
then (inner_extract (remain_i - 1) (h::acc) t) @
(inner_extract remain_i acc t)
else [acc]
in
inner_extract i [] l;;
val extract : int -> 'a list -> 'a list list = <fun>
哦？强啊，List.map (fun l -> h :: l) 避免了把这次运行选中的元素一步一步传下去，也就不会逆序了，也不需要一个内部函数来做递归了，可以的。不过他这个没做剪枝，倒是更简洁了。
# let rec extract k list =
if k <= 0 then [[]]
else match list with
| [] -> []
| h :: tl ->
let with_h = List.map (fun l -> h :: l) (extract (k - 1) tl) in
let without_h = extract k tl in
with_h @ without_h;;
val extract : int -> 'a list -> 'a list list = <fun>
28. Group the Elements of a Set Into Disjoint Subsets
Group the elements of a set into disjoint subsets
- In how many ways can a group of 9 people work in 3 disjoint subgroups of 2, 3 and 4 persons? Write a function that generates all the possibilities and returns them in a list.
- Generalize the above function in a way that we can specify a list of group sizes and the function will return a list of groups.
又可以复用上一题的了，不止上一题的了。
我的解法存在问题，处理存在重复元素的列表时行为无法预期。
这个 flatten 感觉是多余的，它是从 right extract 里带的，但列表嵌套的有点太复杂了我不知道怎么能省略处理掉。
let group l [left_num; right_num] =
let rec remove_list ori_l to_remove_l = match ori_l with
| [] -> []
| h::t -> if (List.exists (fun e -> e = h) to_remove_l)
then remove_list t to_remove_l
else h::(remove_list t to_remove_l)
in
let rec extract k list =
if k <= 0 then [[]]
else match list with
| [] -> []
| h :: tl ->
let with_h = List.map (fun l -> h :: l) (extract (k - 1) tl) in
let without_h = extract k tl in
with_h @ without_h
in
List.map
(fun left_group ->
let new_l = (remove_list l left_group) in
List.map (fun right_group-> left_group :: [right_group]) (extract right_num new_l)) (extract left_num l)
哦，可以用 concat_map 代替 map，出来的结果就直接打平了。
题意是任意数量的组，我想错了，只支持两个组。
标准答案不是我的剔除方案，是分配每一个元素给所有可能性，自然也不存在重复的问题，对于 list 的长度 n 也是遍历，O(n) 的，总的时间复杂都我不太会算。牛啊，用了好多东西，有点看不懂了。
# (* 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_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;;
val group : 'a list -> int list -> 'a list list list = <fun>
不过总是有元素不分配给任意列表的情况，会有很多没填满的情况，都在最后一步被去重了。
29. Sorting a List of Lists According to Length of Sublists
Sorting a list of lists according to length of sublists.
- We suppose that a list contains elements that are lists themselves. The objective is to sort the elements of this list according to their length. E.g. short lists first, longer lists later, or vice versa.
- Again, we suppose that a list contains elements that are lists themselves. But this time the objective is to sort the elements of this list according to their length frequency; i.e., in the default, where sorting is done ascendingly, lists with rare lengths are placed first, others with a more frequent length come later.
来了，排序。函数式让排序变得复杂了，交换元素不太容易，导致很多类 sort 难以使用，我直接用了插入类的排序。
let length_sort l=
let rec insert p last_index_length list=
let length = (List.length p) in
match list with
| [] -> [p]
| h :: t ->
let this_index_length = List.length h in
if length > last_index_length && length <= this_index_length
then p::h::t
else h::(insert p this_index_length t)
in
let rec inner_sort list res= match list with
| [] -> res
| h::t -> inner_sort t (insert h 0 res)
in
inner_sort l []
做到这感觉能做一个函数式的通用排序的，很神秘。哦，傻了库函数有的，哎，又在搞自己。
偷个懒吧 。我的第一步排序应该是浪费了的，
let frequency_sort l =
let rec o_l list cur_length cur_length_list = match list with
| [] -> [cur_length_list]
| h::t -> if (List.length h)=cur_length then (o_l t cur_length (h::cur_length_list))
else if (List.length cur_length_list)!=0
then cur_length_list::(o_l t (List.length h) [h])
else (o_l t (List.length h) [h])
in
let sort_by_len = List.sort (fun a b-> if List.length a>List.length b then 1 else if List.length a=List.length b then 0 else -1)
in
let over_l = o_l (sort_by_len l) 0 [] in
let over_sort_l = sort_by_len over_l in
List.flatten over_sort_l
Error: This expression has type 'a list list list
but an expression was expected of type 'a list list
The type variable 'a occurs inside 'a list
给我整懵了， ‘a list list list 不是 ‘a list list？用我自己写的 length_sort 是可以使用的。。。我不太理解了。
let frequency_sort l =
let rec o_l list cur_length cur_length_list = match list with
| [] -> [cur_length_list]
| h::t -> if (List.length h)=cur_length then (o_l t cur_length (h::cur_length_list))
else if (List.length cur_length_list)!=0
then cur_length_list::(o_l t (List.length h) [h])
else (o_l t (List.length h) [h])
in
let sort_by_len = List.sort (fun a b-> if List.length a>List.length b then 1 else if List.length a=List.length b then 0 else -1)
in
let over_l = o_l (sort_by_len l) 0 [] in
List.flatten (length_sort over_l)
标准答案确实少了我的第一步 sort，改用了一个元组带着 list 的长度再排序。
(* We might not be allowed to use built-in List.sort, so here's an
eight-line implementation of insertion sort — O(n²) time
complexity. *)
let rec insert cmp e = function
| [] -> [e]
| h :: t as l -> if cmp e h <= 0 then e :: l else h :: insert cmp e t
let rec sort cmp = function
| [] -> []
| h :: t -> insert cmp h (sort cmp t)
(* Sorting according to length : prepend length, sort, remove length *)
let length_sort lists =
let lists = List.map (fun list -> List.length list, list) lists in
let lists = sort (fun a b -> compare (fst a) (fst b)) lists in
List.map snd lists
;;
(* Sorting according to length frequency : prepend frequency, sort,
remove frequency. Frequencies are extracted by sorting lengths
and applying RLE to count occurrences of each length (see problem
"Run-length encoding of a list.") *)
let rle list =
let rec aux count acc = function
| [] -> [] (* Can only be reached if original list is empty *)
| [x] -> (x, count + 1) :: acc
| a :: (b :: _ as t) ->
if a = b then aux (count + 1) acc t
else aux 0 ((a, count + 1) :: acc) t in
aux 0 [] list
let frequency_sort lists =
let lengths = List.map List.length lists in
let freq = rle (sort compare lengths) in
let by_freq =
List.map (fun list -> List.assoc (List.length list) freq , list) lists in
let sorted = sort (fun a b -> compare (fst a) (fst b)) by_freq in
List.map snd sorted
总结
有点感觉了。list 类的这几道题我拖了很久才做完，简单的还好，中等的做的我有点汗流浃背了，暂时还没遇到困难的，不知道啥时候能做完。
OCaml 这个类型判断是有问题还是我写的问题？
很多我的和标准答案的答案都有差距啊。
文档信息
- 本文作者：nyaaar
- 本文链接：https://nyaaarlathotep.github.io/2024/08/02/Ocaml-99-%E9%97%AE%E9%A2%98%E7%AC%94%E8%AE%B0/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）