Эффективное проектирование списка списков в F #

Мне нужно сделать проекцию списка списков, который возвращает все комбинации с каждым элементом из каждого списка. Например:

projection([[1]; [2; 3]]) = [[1; 2]; [1; 3]].
projection([[1]; [2; 3]; [4; 5]]) = [[1; 2; 4]; [1; 2; 5]; [1; 3; 4]; [1; 3; 5]].

Я придумал функцию:

let projection lss0 =
    let rec projectionUtil lss accs =
        match lss with
        | []        ->  accs
        | ls::lss'  ->  projectionUtil lss' (List.fold (fun accs' l -> 
                                                        accs' @ List.map (fun acc -> acc @ [l]) accs) 
                                                        [] ls)
match lss0 with
| [] -> []
| ls::lss' ->         
    projectionUtil lss' (List.map (fun l -> [l]) ls)

и тестовый пример:

#time "on";;
let N = 10
let fss0 = List.init N (fun i -> List.init (i+1) (fun j -> j+i*i+i));;
let fss1 = projection fss0;;

Сейчас функция работает довольно медленно, с N = 10 она занимает более 10 секунд. Более того, я думаю, что решение неестественно, потому что я должен разбить один и тот же список двумя разными способами. Есть ли предложения, как я могу улучшить производительность и читаемость функции?

10
задан Benjol 1 June 2011 в 09:58
поделиться