get the minimum element in list using erlang

Erlang Programming Exercises 給了一個要找出 lists1:min(L) 的習題

Erlang Example: Min and Max Element of a List 給出了一個超簡單的答案
-module(mylists).
-export([max/1]).
max([H|T]) ->
    max(H, T).
max(M, []) ->
    M;
max(M, [H|L]) when M > H ->
    max(M, L);
max(_M, [H|L]) ->
    max(H,L).

簡單地說，就是把 List 拆成 M|T，然後再把 T 分成 H|L，也就是 M,H,L，如果M>H，就繼續計算 max(M,L)，如果是其他狀況，就計算 max(H,L)

一開始，我沒辦法想出這個樣子的解法。

不過後來參考了 qsort

qsort([]) -> [];
qsort([Pivot|T]) ->
 qsort([X || X <- T, X < Pivot])
 ++ [Pivot] ++
 qsort([X || X <- T, X >= Pivot]).

想出了另一種解法

max([]) -> [];
max([H|[]]) -> H;
max([Pivot|T]) ->
    L = [X || X <- T, X >= Pivot],
    case length(L)>0 of
        true -> max(L);
        false -> Pivot
    end.
 

重點是 L = [X || X <- T, X >= Pivot] 可以取得所有比 Pivot還大的 list，但如果得到的結果是空的 list，那就代表，最大的元素是 Pivot。


Programming exercises 也給了兩個答案

list1.erl 是比較直覺，看得懂的例子，但缺點是min_max 必須traverse list 兩次

-module(list1).
-export([min/1,max/1,min_max/1]).

min([H | T]) -> min(T, H).

min([], CurrentMin) -> CurrentMin; 
min([H | T], CurrentMin) -> 
  if   
       H < CurrentMin -> min(T, H); 
       true -> min(T,CurrentMin) 
    end.          

max([H | T]) -> max(T, H).

max([], CurrentMax) -> CurrentMax; 
max([H | T], CurrentMax) -> 
  if 
      H > CurrentMax -> max(T, H); 
        true -> max(T,CurrentMax) 
    end.          

min_max(L) -> {min(L), max(L)}.

list2是改進的版本，裡面使用了這個list的函數，min_max 只traverse list 一次，就同時把 min, max 的兩個元素都找出來

foldl(Fun, Acc0, List) -> Acc1
Fun這個函數有兩個參數
第一個參數是List中的元素，第二個參數是Fun函數執行完後的返回值，這個參數第一次執行時
就是Acc0
例子：對[1,2,3,4,5]求和
lists:foldl(fun(X, Sum) -> X + Sum end, 0, [1,2,3,4,5]).
結果：15
執行過程：首先，Fun第一次執行時，X的值取列表List的第一個元素1，Sum取0,
  Fun第二次執行時，X的值取列表List的第二個元素2，Sum取Fun第一次的返回值
  依次輪推，直到List中每個元素執行完，最後foldl返回最後一次的結果。


%%% Code: list2.erl

-module(list2).
-export([min/1,max/1,min_max/1]).

min([H | T]) -> lists:foldl(
  fun(X,Acc)->if X X; true->Acc end end, H, T).

max([H | T]) -> lists:foldl(
  fun(X,Acc)->if X>Acc -> X; true->Acc end end, H, T).

min_max([H | T]) -> lists:foldl(
  fun(X,{MinAcc,MaxAcc}) -> 
    if 
      X < MinAcc, X < MaxAcc -> {X, MaxAcc};
      X > MinAcc, X < MaxAcc -> {MinAcc, MaxAcc};
      X > MinAcc, X > MaxAcc -> {MinAcc, X}
    end
  end, {H,H}, T).