2010-10-21 25 views
6

Listeler listesinin, n x p öğesinin p x n'a dönüştürülmesini sağlamak için özyinelemeli bir işlev yapmaya çalışıyorum. Ama bunu yapamam. Bir n x 3 bire listelerin bir 3 x n listesini devrik için bir işlev yapmak mümkün oldum:listelerin bir listesini aktarma

let rec drop1 list= 
    [(match (List.nth list 0) with [] -> [] | a::b -> b); 
    (match (List.nth list 1) with [] -> [] | a::b -> b); 
    (match (List.nth list 2) with [] -> [] | a::b -> b);] 

let rec transpose list= 
    if List.length (List.nth list 0) == 0 then [] 
    else [(match (List.nth list 0) with [] -> 0 | a::b -> a); 
      (match (List.nth list 1) with [] -> 0 | a::b -> a); 
      (match (List.nth list 2) with [] -> 0 | a::b -> a)] 
     :: transpose (drop1 list) 

Ama bunu genellemek mümkün değilim. Kesinlikle yanlış yönde düşünüyorum. Bu genelleştirilebilir mi? Daha iyi bir çözüm var mı? Lütfen yardım et.

cevap

10
let rec transpose list = match list with 
| []    -> [] 
| [] :: xss -> transpose xss 
| (x::xs) :: xss -> 
    (x :: List.map List.hd xss) :: transpose (xs :: List.map List.tl xss) 
+1

+1, Wow! List.map işlevinin farkında değildim. Kılavuz, kuyruk özyineli olmadığını söylüyor. Bunu daha büyük bir kodla kullanırsam ne etkisi olabilir? – lalli

+1

@lalli: Çok büyük listeler için yığın taşmasına neden olabilir. Bu durumda, bunun yerine 'List.rev_map' kullanmalı ve sonunda listelerden geçmeli ve bunları tersine çevirmelisiniz. Bununla birlikte, 'transpose' tanımımın aynı zamanda kuyruk özyineli olmadığını da unutmayın (sizinki de değil). – sepp2k

+4

Önce kuyruk özyineliği hakkında endişelenmemelisiniz; basit ve açık bir uygulamaya sahip olmayı deneyin. Çok büyük listelere sahip bir "devir" işlevinin ('liste listesi') kullanılması büyük olasılıkla çok kötü bir fikirdir. Çok fazla veriye sahipseniz, başka bir veri yapısı (örneğin, bir sabit zamana sahip olan "transpose" işlevi olan (int * int) tarafından indekslenen bir matris) muhtemelen daha uygundur. – gasche

İlgili konular