將值過濾到兩個列表中

Question

所以我是新來的sml，並且試圖理解ins/out。最近我嘗試創建一個帶兩個參數的過濾器：一個函數（返回一個布爾值）以及一個針對該函數運行的值列表。過濾器所做的是返回對該函數返回true的值列表。

代碼：

fun filter f [] = [] | 
    filter f (x::xs) = 
     if (f x) 
     then x::(filter f xs) 
     else (filter f xs); 

使作品。但是我現在想要做的僅僅是返回一個包含真值列表的元組，以及false。我被困在我的條件上，我真的不能看到另一種方式。有關如何解決這個問題的任何想法？

代碼：

fun filter2 f [] = ([],[]) | 
    filter2 f (x::xs) = 
     if (f x) 
     then (x::(filter2 f xs), []) (* error *) 
     else ([], x::(filter2 f xs)); (* error *) 

Answer 1

所以我會表現出很好的辦法做到這一點，和更好的方法來做到這一點（IMO）。但是，「更好的方式」只是供將來參考，當你學會：

fun filter2 f [] = ([], []) 
    | filter2 f (x::xs) = let 

    fun ftuple f (x::xs) trueList falseList = 
    if (f x) 
     then ftuple f xs (x::trueList) falseList 
    else ftuple f xs trueList (x::falseList) 

    | ftuple _ [] trueList falseList = (trueList, falseList) 

in 
    ftuple f (x::xs) [] [] 
end; 

之所以你不工作的，因爲當你打電話x::(filter2 f xs)，編譯天真地假設你正在建設一個列表，它不假定它是一個元組，它是進入函數調用的範圍。所以當你自己想想結果類型是列表的結果類型，編譯器得到隧道視覺，並認爲結果類型是列表。在我看來，這是更好的版本，如果你很好奇，你應該查看功能foldr，使用這種技術要好得多，因爲它更具可讀性，更簡潔，更重要的是...... 更具可預測性，穩健：

fun filter2 f l = foldr (fn(x,xs) => if (f x) then (x::(#1(xs)), #2(xs)) else (#1(xs), x::(#2(xs)))) ([],[]) l; 

爲什麼第一個示例是因爲你存儲的是積累，要麼符合條件或不符合條件的變量的副本默認爲空名單的原因。但是，您必須明確告訴SML編譯器確保類型規則同意。你必須確保SML知道你的返回類型是列表的元組。這條命令鏈中有任何錯誤，這將導致執行失敗。因此，在使用SML時，總要研究你的類型推斷。至於第二個，你可以看到它是一個單線，但我會留給你自己研究一個，只有谷歌foldr和foldl。

Answer 2

我認爲有幾種方法可以做到這一點。

氣浮法處理

例如，我們可以使用基於這樣的事實，你的元組會由兩個要素構成一個歸納的方法，首先是滿足謂詞的元素的列表，第二個不包含的元素列表。所以，你可以重用你的過濾器功能：

fun partition f xs = (filter f xs, filter (not o f) xs) 

這是不是最好的方法，不過，因爲它會評估名單的兩倍，但如果名單是小的，這是很明顯的並且十分易讀。

摺疊

另一種方式來思考這是褶皺的條款。你可能認爲你將列表縮減爲一個元組列表，並且隨着時間的推移，你會根據謂詞來分割項目。 Somwewhat這樣的：

fun parition f xs = 
    let 
     fun split x (xs,ys) = 
      if f x 
      then (x::xs,ys) 
      else (xs, x::ys) 

     val (trueList, falseList) = List.foldl (fn (x,y) => split x y) 
                ([],[]) xs 
    in 
     (List.rev trueList, List.rev falseList) 
    end 

分區之前

你也可以實現自己的摺疊算法相同的方式，SML的List.parition方法做：

fun partition f xs = 
    let 
     fun iter(xs, (trueList,falseList)) = 
      case xs of 
       [] => (List.rev trueList, List.rev falseList) 
       | (x::xs') => if f x 
          then iter(xs', (x::trueList,falseList)) 
          else iter(xs', (trueList,x::falseList)) 
    in 
     iter(xs,([],[])) 
    end 

使用SML依據方法

最終，您可以避免所有這些並使用SML方法List.partition其文檔說：

分區FL

將f到每個元素x升的，從左至右，然後返回 對（正，負），其中pos是那些列表x其中fx 評估爲真，neg爲fx 評估爲false的列表。 pos和neg的元素保留與他們在l中擁有的相對順序相同的 。

該方法與前面的例子一樣。