изграждане на списък от int в ocaml

Искам да напиша функция, която изгражда списък между две int, включително

rec myFunc x y ще изгради списък с всички int между x и y, включително x и y

За логиката в момента имам нещо подобно:

let rec buildList i n = let x = i+1 in if i <= n then i::(buildList x n)

Но това ми дава грешка „Изразът има тип „списък, но се очакваше израз от тип единица.

Мислех, че buildList връща списък с int, а i като int, така че операторът cons би бил валиден, но казва, че трябва да е невалиден?

Защо се случва това и как да го поправя?


list int ocaml
person Michael L    schedule 13.04.2011    source източник

Отговори (5)


arrow_upward
7
arrow_downward

Ако условието е вярно, връщате списъка i::(buildList x n). Ако не е вярно, какво връщате?

Добавете else [] към вашата функция, за да върнете празния списък, когато условието не е изпълнено. Когато нямате else, компилаторът предполага, че е else () (оттук и съобщението за грешка).

person Laurent    schedule 13.04.2011
comment
Уау, напълно го пропуснах. Благодаря - person Michael L; 13.04.2011

arrow_upward
3
arrow_downward

Във вашия if липсва условие else

Предлагам ви да използвате рекурсивна функция на опашката:

let buildList x y =
  let (x,y) = if x<y then (x,y) else (y,x) in
  let rec aux cpt acc =
      if cpt < x then acc
      else aux (cpt-1) (cpt::acc)
  in aux y []

Първо се уверете, че сте подредили вашите граници правилно (идиотско доказателство) и след това конструирайте списъка благодарение на локална рекурсивна функция, която взема акумулатор.

person Hugo    schedule 14.04.2011

arrow_upward
1
arrow_downward

Две алтернативи, разчитащи на пакета на батериите,

Използване на разгъване, чиято цел е да се изгради списък,

let range ~from:f ~until:u = 
    BatList.unfold f (function | n when n <= u -> Some (n, succ n) | _ -> None)

Използвайки Enum, позволяващ работа с мързелива структура от данни,

# BatList.of_enum @@ BatEnum.(1--9);;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]
person zurgl    schedule 13.02.2014

arrow_upward
0
arrow_downward

Моето предложение, това спазва реда на аргументите.

let rec iota n m = 
  let oper = if n < m then succ else pred  in 
    if n = m then [n] else n :: iota (oper n) m

Редактиране:

Изборът на оператор е вътре в рекурсивната част, по-добре трябва да е отвън така:

let iota n m = 
  let oper = if n < m then succ else pred  in 
    let rec f1 n m = if n = m then [n] else n :: f1 (oper n) m in
      f1 n m

При повече от 200 000 елемента получавам препълване на стека (така че ето ни)

# iota 0 250000;;
Stack overflow during evaluation (looping recursion?).

Todo: опашка рекурсия

person Str.    schedule 12.02.2014

arrow_upward
0
arrow_downward 

let buildList i n =
 let rec aux acc i =
   if i <= n then
     aux (i::acc) (i+1)
   else (List.rev acc)
 in
 aux [] i

Тест:

# buildList 1 3;;
- : int list = [1; 2; 3]
# buildList 2 1;;
- : int list = []
# buildList 0 250000;;
- : int list =
[0; 1; 2; 3; .... 296; 297; 298; ...]
person V. Michel    schedule 11.12.2016