SML - 在列表中查找出現以形成有序對

我正在嘗試在SML中編寫一個函數，該函數需要一個ints列表，並且會輸出一個有序的ints對列表。有序對第一個int是輸入列表中發生的int，有序對中的第二個int是它在輸入列表中發生的次數。此外，返回的列表應該按照有序對中的第一個int升序排列。SML - 在列表中查找出現以形成有序對

例如輸入列表[1, 1, 1, 2, 3, 3, 5]將輸出爲[(1,3), (2, 1), (3, 2), (5, 1)]。

到目前爲止，我有一個使用foldl

修訂，因爲原來的職位代碼的功能。

fun turnIntoPairs l = foldl (fn (e, a) => if List.exists (fn (x, _) => x = e) a then x + 1 else a @ [(e, 1)]) [] l;

我無法更新在那裏我找到了有序對已在列表中的列表 - 我想補充一個在有序對第二個INT被發現，而它仍然在列表中。

任何幫助將不勝感激！

C:\Program Files (x86)\SMLNJ\\bin\.run\run.x86-win32.exe: Fatal error -- Uncaught exception Error with 0 
raised at ../compiler/TopLevel/interact/evalloop.sml:66.19-66.27 

[autoloading done] 
C:\Users\Localadmin\Desktop\CS 671\Program 3\commonFactors.sml:1.87 Error: unbound variable or constructor: x 
C:\Users\Localadmin\Desktop\CS 671\Program 3\commonFactors.sml:1.44-1.110 Error: types of if branches do not agree [literal] 
then branch: int 
else branch: (''Z * int) list 
in expression: 
    if (List.exists (fn <pat> => <exp>)) a 
    then <errorvar> + 1 
    else a @ (e,1) :: nil 
[Finished in 0.5s with exit code 1]

來源

2013-06-28 Andrew_CS

看看你的錯誤。它抱怨'find'和'x'不存在。通過'find'我認爲你的意思是'List.find'，儘管那個類型的簽名不適合你試圖給它的參數。 – Tayacan

此外，同樣的問題正在回答[here]（http：// stackoverflow。com/questions/17372083/turn-a-list-with-common-items-in-to-a-list-of-ordered-pairs） – Tayacan

我看到那篇文章，當我發佈這篇文章時，我正在寫這個問題。我用這些信息開始寫這個功能，我現在遇到了麻煩。 –

不能確定如何解決當前的程序，但你可以通過在兩個分裂它解決了這個問題：分組相等的元素，然後排序列表。

(* Groups successive equal elements into a tuples (value, count) *) 
fun group (l as (x :: _)) = 
    let val (firstGroup, rest) = List.partition (fn y => x = y) l 
    in 
     (x, List.length firstGroup) :: (group rest) 
    end 
    | group [] = [] 

(* Now that we have our elements grouped, what's left is to order 
    them as required. *) 
fun turnIntoPairs xs = 
    ListMergeSort.sort (fn ((x, _), (y, _)) => x >= y) (group xs)

來源

2013-06-28 21:01:13 MisterMetaphor

謝謝你的替代解決方案。理想情況下，我想修復自己的代碼，這樣我就可以更好地理解foldl的工作方式，所以我不只是抄襲其他人。不錯的解決方案！ –

就讓我們來看看你傳遞給foldl功能：

(fn (e, a) => if List.exists (fn (x, _) => x = e) a then x + 1 else a @ [(e, 1)])

的第一個問題（該類型檢查的抱怨）是你的if表達式返回要麼x + 1，或a @ [(e, 1)]，由於前者是int類型的值並且後者是(int * int) list類型的值，所以這似乎是有問題的。

讓我們使用，我不會定義，看看它是否變得更清晰了一些輔助功能，重寫代碼：

(fn (e, a) => if List.exists (fn (x, _) => x = e) a then increment a e else a @ [(e, 1)])

凡increment有型(int * int) list -> int -> (int * int) list。

你能實施increment嗎？

來源

2013-06-28 22:40:36 Gian

我不認爲我可以實現該方法，因爲當我嘗試調用x增加時遇到了x未知的錯誤？ –

對不起，本來是'e'，而不是'x'。更新。 – Gian

和Gian一樣，我寧願把它分成兩個函數：一個是摺疊和一個插入的輔助函數。順便說一句，插入函數將採用一個元素和一個現有的(int * int) list，就像fold的accumulator函數接受這兩個參數一樣。

通常我會寫一個插入功能咖喱（即insert x xs），但如果我把它寫uncurried（即insert (x, xs)），我可以直接將它傳遞給foldl：

fun insert (x, [])   = [(x,1)] 
    | insert (x, ((y,c)::xs)) = 
    if x = y then (y,c+1)::xs else (y,c)::insert (x, xs) 

fun turnIntoPairs xs = foldl insert [] xs

來源

2013-07-21 12:41:28

SML - 在列表中查找出現以形成有序對

回答

相關問題