Вернуть элемент в позиции x в списке - PullRequest
Новая
       27

Вернуть элемент в позиции x в списке

1 голос
/ 17 апреля 2011

Я читал этот пост Хотя или Tail Recursion в F #, что использовать, когда? Несколько человек сказали, что «функциональный способ» состоит в использовании карт / фолдов и функций более высокого порядка. повторения и зацикливания.

У меня есть эта функция, которая возвращает элемент в позиции x в списке: 

let rec getPos l c =  if c = 0 then List.head l else getPos (List.tail l) (c - 1)

как его можно превратить в более функциональный?

Ответы [ 5 ]

5 голосов
/ 17 апреля 2011

Это примитивная функция списка (также известная как List.nth).

Можно использовать рекурсию, особенно при создании базовых строительных блоков.Хотя было бы лучше с сопоставлением с шаблоном вместо if-else, например: 

let rec getPos l c =
   match l with
   | h::_ when c = 0 -> h
   | _::t -> getPos t (c-1)
   | [] -> failwith "list too short"

Эту функцию можно выразить с помощью List.fold, однако результат менее ясен, чем рекурсивная версия.

1 голос
/ 17 апреля 2011

Если вы хотите использовать для этого функции высокого порядка, вы можете сделать: 

let nth n = Seq.take (n+1) >> Seq.fold (fun _ x -> Some x) None

let nth n = Seq.take (n+1) >> Seq.reduce (fun _ x -> x)

Но на самом деле идея состоит в том, чтобы иметь базовые конструкции и комбинировать их для построения того, что вы хотите. Получение n-го элемента последовательности, очевидно, является основным блоком, который вы должны использовать. Если вам нужен n-й предмет, как упомянул Бенджол, сделайте myList.[n].

Для построения базовых конструкций нет ничего плохого в использовании рекурсивных или изменяемых циклов (и часто у вас есть , чтобы сделать это таким образом).

1 голос
/ 17 апреля 2011

Ваше определение уже довольно функционально, так как оно использует хвостовую рекурсивную функцию вместо конструкции императивного цикла.Тем не менее, это также похоже на то, что программист Scheme мог бы написать, потому что вы используете head и tail.

Я подозреваю, что вы действительно спрашиваете, как написать это в более идиоматическом стиле ML.Ответ заключается в использовании сопоставления с образцом: 

let rec getPos list n =
    match list with
    | hd::tl ->
        if n = 0 then hd
        else getPos tl (n - 1)
    | [] -> failWith "Index out of range."

Рекурсия по структуре списка теперь раскрывается в коде.Вы также получаете предупреждение, если сопоставление с образцом не является исчерпывающим, поэтому вы вынуждены иметь дело с слишком большой ошибкой индекса.

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

Конечно, Бенджол прав, на практике вы просто пишете mylist.[n].

1 голос
/ 17 апреля 2011

Я не уверен, что вы подразумеваете под более функциональным.

Вы сами катаете это как учебное упражнение?

Если нет, вы можете просто попробовать это: 

> let mylist = [1;2;3;4];;
> let n = 2;;
> mylist.[n];;
0 голосов
/ 17 апреля 2011

Не как практическое решение, а как упражнение, вот один из способов выразить nth через foldr или, в терминах F #, List.foldBack: 

let myNth n xs =
    let step e f = function |0 -> e |n -> f (n-1)
    let error _ = failwith "List is too short"
    List.foldBack step xs error n
...