F # найти минимальную функцию с List.fold - PullRequest
Новая
       7

F # найти минимальную функцию с List.fold

0 голосов
/ 29 октября 2018

Мне нужна функция, которая находит минимальный элемент списка, реализующий модуль List.fold. Я знаю, что могу использовать List.min, но для этого упражнения мне нужно, чтобы он был List.fold. Пока у меня есть: 

let findMin list min = function
     | [ ] -> min
     | head::tail ->  list |> List.fold( fun acc -> min)  //missing conditional inside fold to determine min

Я не привык к функциональному программированию, обычно в Java я бы делал что-то вроде этого: 

 public int getMin (){

  int min = head.data;
  Node curr = head.next;

  while (! ( curr  == NULL ) ){
     if ( curr.data < min) 
          min = curr.data;

      curr = curr.next; 
   }

   return min;
 }

Но так как F # работает с неизменяемыми константами, я не могу переназначить мин. Я нашел примеры сгибов, используемых для подсчета или суммирования элементов в списке, но ни один из них не находит минимальный или максимальный элемент. У меня проблемы именно с условной логикой внутри модуля, и если кто-то может мне помочь, я буду очень признателен. Заранее спасибо.

Ответы [ 4 ]

0 голосов
/ 30 октября 2018

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

// это папка, вызываемая функцией List.fold, получает текущий минимум и элемент

let folder a b = если a // получает список и возвращает минимум с помощью модуля List.fold

let fold list = List.fold (забавный элемент -> папка соотв. Элемент) (список List.head) список

0 голосов
/ 29 октября 2018

Вам не нужно иметь дело со случаем, когда входной список пуст, потому что List.fold возвращает начальное значение в этом случае. Обычно мы передаем System.Int32.MaxValue в качестве начального значения.

Вот код длинной версии: 

let min a b = if a < b then a else b

let minOfList initialValue theList =
    theList
    |> List.fold
        (fun currentMin x ->
            let newMin = min currentMin x
            newMin)
        initialValue

let result = minOfList System.Int32.MaxValue [34; -1; 21; 99]
printfn "%d" result // -1

И короткий код: 

let min a b = if a < b then a else b
let minOfList = List.fold min
let result = minOfList System.Int32.MaxValue [34; -1; 21; 99]
printfn "%d" result // -1
0 голосов
/ 29 октября 2018

Вы можете использовать аккумулятор в качестве значения, которому вы обычно назначаете минимальное значение.

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

Используя встроенную функцию min, вы можете написать 

let findMin list = List.fold min System.Int32.MaxValue list

min - функция, применяемая к каждому предмету и аккумулятору

System.Int32.MaxValue - исходное значение аккумулятора, начальное число

Вы также можете использовать List.reduce, что то же самое, но он использует первый элемент списка в качестве начального числа. 

let findMin list = List.reduce min list

В идеале вы должны обернуть это во что-то, что обрабатывает случай пустого массива, потому что fold вернет начальное значение и reduce вызовет исключение.

0 голосов
/ 29 октября 2018

Концепция сгиба проста: вы выполняете функцию, называемую функцией folder, по списку. При каждом вызове функция folder получает элемент из списка и состояние и возвращает обновленное состояние.

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

подпись сгиба: 

List.fold :
   folder: 'State -> 'T -> 'State ->
   state : 'State  ->
   list  : 'T list 
        -> 'State

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

Итак, ваша folder функция должна выглядеть примерно так: 

let folder min currData = ...

и ваша minimum функция должна выглядеть следующим образом: 

let minimum ls =
    ls
    |> List.fold folder initial

и вы называете это так: 

minimum [ 5 ; 3 ; 8]
|> printfn "%A"  // outputs: 3

Осталось несколько вопросов о том, как обращаться с начальным значением и что происходит, если список пуст. Но я оставлю это тебе.

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

...