OCaml - функция, которая возвращает все префиксы списка

Для [1;2;3], я хочу вернуть [[]; [1]; [1; 2]; [1; 2; 3]]. Я врезался в стену и мне нужна помощь, это то, что я сделал до сих порOCaml - функция, которая возвращает все префиксы списка

let rev list = 
let rec aux acc = function 
    | [] -> acc 
    | h::t -> aux (h::acc) t in 
aux [] list;; 

let prefixes xs = 
let xs = rev xs in 
let rec xs = function 
    |[] -> [[]] 
    |hd::tl -> xs:: tl in 
xs ;;`

Пожалуйста, помогите мне, я знаю, что, вероятно, большинство из того, что я сделал до сих пор не так.

источник

2014-11-06 Thanospan

Вот решение, которое я нашел. Хотя это, вероятно, не самый лучший, так как мне нужно в конце списка перевернуть список.

let prefix l = List.rev (List.fold_left (fun acc itt -> ((List.hd acc)@[itt])::acc) [[]] l);;

источник

2014-11-07 00:34:37

Можете ли вы ходить меня бросило, что вы сделали, потому что я являюсь действительно новым для OCaml – Thanospan

@Thanospan Я собираюсь предположить, что ваш знакомый со складкой. Если вы не посетите [это] (http://www.cs.cornell.edu/courses/cs3110/2011sp/recitations/rec05.htm). Поэтому внутри List.fold_left itt будет элемент l. Например, в первый раз это будет 1, затем 2, затем 3 ... acc - это то, что вы сейчас имеете, и оно начинается с [[]] пустого списка списка. Так что давайте скажем, что мы находимся в itt = 1, тогда глава acc будет []. Мы констатируем, что голова к itt = 1 должна сделать [1]. acc будет сохранен как [[1]; []] Мы делаем, что новый глава acc. Поэтому, когда fold_left снова повторяет, чтобы itt = 2, головка acc будет [1]. ** next ** –

Снова возьмем голову = [1] и сравним его с [2]. Итак, мы имеем [1; 2] и сохраняем новый acc как [[1; 2]; [1]; []]. Таким образом, вы можете увидеть основную идею. Когда itt = l [n], где l [n] - n-я позиция списка l. Мы хотим, чтобы головка acc была списком с элементами l [0]; l [1]; ..; l [n-1] (содержащий все элементы до, но не включая l [n]). Затем мы объединим эти два, чтобы сделать наш желаемый список содержащим все элементы l [0] равными l [n]. Тогда в основном добавьте это к вершине acc. В конце список фактически отменен, поэтому я вызываю List.rev, чтобы отменить его. Не стесняйтесь спрашивать, запутались ли вы. –

Обычный вопрос, который вы хотите задать, - это то, как вы можете получить префиксы списка с заданной функцией, которая возвращает все префиксы более короткого списка.

Скажите, что ваш список: [1; 2; 3]. Более короткий список будет [2; 3]. Все префиксы этого сокращенного списка: [], [2], и [2;3]. Как вы могли получить нужный список префиксов из этого списка? Это выглядит довольно прямолинейно: вам просто нужно добавить 1 к передней части всех из них. Кроме того, вам нужно добавить новый пустой префикс.

В качестве базового варианта список всех префиксов [] - это просто [].

Это похоже на работоспособный способ решения проблемы, за исключением того, что лучший способ сделать это - использовать функцию из модуля List. Поскольку это выглядит как домашнее задание, я не уверен, что это разрешено.

Надеюсь, это поможет.

В качестве побочного комментария ваша функция rev выглядит хорошо для меня. Но вам может не понадобиться, чтобы решить проблему. Возможно, вы могли бы написать свою собственную функцию map.

источник

2014-11-07 00:10:31

Это кажется намного проще, чем решение, опубликованное ранее. Остерегайтесь, что List.map не являются рекурсивными.

let rec prefixes l = match l with 
     [] -> [] 
    | x::xs -> [x] :: (List.map (fun a -> (x :: a)) (prefixes xs));;

источник

2015-10-21 19:28:30

let rec prefixes = function 
     [] -> [[]] 
    | x::tl -> []::List.map (fun li -> x :: li) (prefixes tl);;

Тест:

# prefixes [1];; 
- : int list list = [[]; [1]] 
# prefixes [1;2];; 
- : int list list = [[]; [1]; [1; 2]] 
# prefixes [1;2;3];; 
- : int list list = [[]; [1]; [1; 2]; [1; 2; 3]]

источник

2015-10-21 22:31:58

OCaml - функция, которая возвращает все префиксы списка

ответ

Смежные вопросы