Блог

Главная - Вопросы по программированию - F # Использование рекурсивных списков

F # Использование рекурсивных списков

#f#

#f#

Вопрос:

Мой код (ниже) завершается с исключением переполнения стека. Я предполагаю, что F # не похож на haskell и dosent, которые хорошо работают с рекурсивными списками. Каков правильный способ работы с подобными рекурсивными списками в F #? Должен ли я передать ему значение int, чтобы оно имело определенный размер?

 let rec collatz num =
    match num with 
        |x when x % 2 = 0 ->num :: collatz (x/2)                                            
        |x ->               num :: collatz ((x * 3)   1)

let smallList = collatz(4) |> Seq.take(4)

Комментарии:

1. В дополнение к ответу Дэниела — проблема не в том, что список рекурсивен — это прекрасно в F #. Проблема в том, что список бесконечен , а списки F # по умолчанию не являются ленивыми.

Ответ №1:

Для такого бесконечного списка, как этот, вы хотите вернуть последовательность. Последовательности являются ленивыми; списки — нет.

 let rec collatz num = 
  seq {
    yield num
    match num with 
    | x when x % 2 = 0 -> yield! collatz (x/2)                                            
    | x -> yield! collatz ((x * 3)   1)
  }

let smallList = 
  collatz 4
  |> Seq.take 4
  |> Seq.toList //[4; 2; 1; 4]

Ответ №2:

 let collatz num =
  let next x = if x % 2 = 0 then x / 2 else x * 3   1
  (num, next num)
  |>Seq.unfold  (fun (n, x) -> Some (n, (x, next x)))