通過函數簽名遞歸解壓列表

我正試圖在sml中編寫一個函數，該函數可以解壓縮任意深度的嵌套列表。例如unpack [[[1,2]]應該產生[1,2]。我試圖像：通過函數簽名遞歸解壓列表

樂趣解壓XS =如果nestedp（XS），然後解壓（HD XS）其他XS;

與 fun nestedp [_] = true | nestedp _ = false;

sml不喜歡這樣定義unpack，因爲它推斷出解包類型爲'a list - >'a。調用返回到hd被傳回解壓縮，但它現在不'看到'一個列表，而是一個變量。

是否有可能以這種方式解壓縮嵌套列表？

來源

2011-09-03 fons haffmans

我不認爲sml的類型系統可以處理這個問題。你能想出一種方法來編寫你的函數的類型嗎？我不能（但是從我使用ml開始已經有一段時間了）。 –

基本上它就像'list - >'b列表，其中'a是類型'列表列表（例如）和'b將是'列表（因爲嵌套的一個層次將被刪除）。 –

這是haskell採取 - http://stackoverflow.com/questions/5994051/is-there-a-function-to-flatten-a-nested-list-of-elements - 但它使用「MultiParamTypeClasses」 –

您無法對內置列表類型執行此操作，因爲您無法獲得匹配的類型。

例如，有人可能會認爲它可以使用'a list list -> 'a list類型的函數，然後遞歸應用它，直到它達到非嵌套列表的基本情況。但是，您將無法以任何方式檢測基本情況，導致您的類型不匹配。

你可以，但是，這樣做，如果你創建了自己的列表類型：

datatype 'a nestableList = Cons of 'a * 'a nestableList 
         | NCons of 'a nestableList * 'a nestableList 
         | Nil;

這裏，Cons和Nil將工作一樣::和[]，而NCons將允許嵌套列表建設。

舉個例子：

(* The list [[1, 2], [[3], [4, 5, 6]]] *) 
val nlist = NCons(
       Cons(1, Cons(2, Nil)), 
       NCons(
       NCons(
        Cons(3, Nil), 
        Cons(4, Cons(5, Cons(6, Nil))) 
       ), 
       Nil 
      ) 
      );

然後，您可以拼合此嵌套列表類型是這樣的：

fun flatten nls = 
let 
    fun flatten_ Nil     = [] 
    | flatten_ (NCons(head, tail)) = flatten head @ flatten tail 
    | flatten_ (Cons(head, tail)) = head :: flatten tail 
in 
    flatten_ nls 
end;

，然後可以像這樣

val flattenedNlist = flatten nlist;  (* Yields [1, 2, 3, 4, 5, 6] *)

這裏我使用它會產生一個常規列表，但它可以很容易地被改變爲返回一個相同類型的列表。

來源

2011-09-07 16:35:56

通過函數簽名遞歸解壓列表

回答

相關問題