列表的第一個和最後一個元素OCaml

Question

我想要在OCaml中獲取列表的第一個和最後一個元素。我希望我的功能會像

'a list -> 'a * 'a 

我所試圖做的是

let lista = [1;2;3;4;6;0];; 

let rec first_last myList = 
     match myList with 
     [x] -> (List.hd lista,x) 
     | head::tail ->  
        first_last tail;; 

first_last lista;; 

，因爲我做了列表爲整數，然後我做這句法像

*int list -> int * 'a 

當然

關鍵是我沒有想法如何做'這個功能。

什麼方向？

Answer 1

另一種可能性只有一個功能：

let rec first_last = function 
    | [] -> failwith "too bad" 
    | [e] -> failwith "too bad" 
    | [e1;e2] -> (e1,e2) 
    | e1 :: _ :: r -> first_last (e1::r) 

你可能更喜歡它這樣：

let rec first_last myList = match myList with 
    | [] -> failwith "too bad" 
    | [e] -> failwith "too bad" 
    | [e1;e2] -> (e1,e2) 
    | e1 :: _ :: r -> first_last (e1::r) 

Answer 2

方向是寫兩個不同的功能first和last和實施first_and_last功能：

let first_and_last xs = first xs, last xs 

Answer 3

您可以創建兩個單獨的函數來返回第一個元素和最後一個元素，然後在您的first_and_last函數中返回一個元組（first_element，last_element）。

let rec first_element list = 
    match list with 
     | [] -> failwith "List is empty" 
     | first_el::rest_of_list -> first_el 


let rec last_element list = 
    match list with 
     | [] -> failwith "List is empty" 
     | [x] -> x 
     | first_el::rest_of_list -> last_element rest_of_list 

Answer 4

您可以創建具有空列表的基本情況的輔助功能 - 爲它返回自身，否則檢查，如果接下來的遞歸調用將返回一個空列表。如果是這樣，返回當前元素（這是定義列表中的最後一個元素），如果沒有，返回遞歸調用返回的內容。

對於常規（非幫助）方法，如果列表至少包含一個元素（即hd::tl = hd::[]），那麼您可以將從last函數獲得的列表連接到ls的頭部。

可以實現如下：

let rec last ls = 
    match ls with 
    | [] -> [] 
    | hd::tl -> let next = last tl in 
     if next = [] then [hd] 
    else next 
;; 
let first_last ls = 
    match ls with 
    | [] -> failwith "Oh no!!!!! Empty list!" 
    | hd::tl -> hd::last tl 
;; 

Answer 5

另一個拿這個問題。

let first_last xs = 
    let rec last_non_empty = function 
    | [x]  -> x 
    | _ :: xs' -> last_non_empty xs' 
    | []  -> failwith "first_last: impossible case!" 
    in 
    match xs with 
     | [] -> failwith "first_last" 
     | x::_ -> (x, last_non_empty xs) 

該實現方式的一些性質： （1）它符合規範'a list -> 'a * 'a：

utop > #typeof "first_last";; 
val first_last : 'a list -> 'a * 'a 

（2）它爲單列表：first_last [x] = (x,x)：

utop> first_last [1];; 
- : int * int = (1, 1)                                 utop> first_last ["str"];; 
- : bytes * bytes = ("str", "str") 

（3 ）它是尾遞歸的（因此，對於足夠大的列表，它不會導致堆棧溢出）：

utop > first_last (Array.to_list (Array.init 1000000 (fun x -> x+1)));; 
- : int * int = (1, 1000000) 

（4）它只遍歷輸入列表一次; （5）它避免了在遞歸階梯中創建新列表; （6）避免污染名稱空間（價格不允許重用像last這樣的函數）。

---

而另一個相當簡單的變型，從第一原則（我是想說明在SICP書的精神「如意算盤」）：

(* Not tail-recursive, might result in stack overflow *) 
let rec first_last = function 
    | [] -> failwith "first_last" 
    | [x] -> (x,x) 
    | x :: xs -> (x, snd (first_last xs))