Wederzijds recursieve functies

Wederzijds recursieve functies

Basis

Je kan de functie is_even en de functie is_oneven op een wederzijds recursieve manier definiëren als volgt:

let rec is_even n =
  if n = 0 then true else is_oneven (n - 1)
and is_oneven n =
  if n = 0 then false else is_even (n - 1)

Tekstvoorstellingen van uitdrukkingen ontleden

We definiëren de volgende begrippen:

• We noemen de getal-uitdrukkingen en de uitdrukkingen tussen haakjes de primaire uitdrukkingen.
• Een primaire uitdrukking is ook een multiplicatieve uitdrukking. (Merk op: deze definitie van "multiplicatieve uitdrukking" verschilt enigszins van die gegeven in Varianttypes.)
• Een multiplicatieve uitdrukking, gevolgd door een maalteken of een gedeeld-door-teken, gevolgd door een primaire uitdrukking, is ook een multiplicatieve uitdrukking.
• Een multiplicatieve uitdrukking is een uitdrukking.
• Een uitdrukking, gevolgd door een plusteken of een minteken, gevolgd door een multiplicatieve uitdrukking, is een uitdrukking.

In symbolen (dit is geen OCaml-notatie, maar wel een vaak gebruikte notatie om de grammaticale regels van programmeertalen te definiëren):

Uitdrukking ::=
  MultiplicatieveUitdrukking
| Uitdrukking + MultiplicatieveUitdrukking
| Uitdrukking - MultiplicatieveUitdrukking

MultiplicatieveUitdrukking ::=
  PrimaireUitdrukking
| MultiplicatieveUitdrukking * PrimaireUitdrukking
| MultiplicatieveUitdrukking / PrimaireUitdrukking

PrimaireUitdrukking ::=
  GetalUitdrukking
| ( Uitdrukking )

We kunnen, gegeven een lijst van tokens, de uitdrukking berekenen die door deze lijst van tokens voorgesteld wordt, als volgt:

let rec splits_uitdrukking_van_tokens tokens =
  let (multUitdr, rest) = splits_mult_uitdrukking_van_tokens tokens in
  splits_uitdrukking_rest_van_tokens multUitdr rest
and splits_uitdrukking_rest_van_tokens uitdr tokens =
  match tokens with
    "+"::rest ->
    let (multUitdr, rest2) = splits_mult_uitdrukking_van_tokens rest in
    splits_uitdrukking_rest_van_tokens (SomUitdrukking (uitdr, multUitdr)) rest2
  | "-"::rest ->
    let (multUitdr, rest2) = splits_mult_uitdrukking_van_tokens rest in
    splits_uitdrukking_rest_van_tokens (VerschilUitdrukking (uitdr, multUitdr)) rest2
  | _ ->
    (uitdr, tokens)
and splits_mult_uitdrukking_van_tokens tokens =
  let (primUitdr, rest) = splits_primaire_uitdrukking_van_tokens tokens in
  splits_mult_uitdrukking_rest_van_tokens primUitdr rest
and splits_mult_uitdrukking_rest_van_tokens uitdr tokens =
  match tokens with
    "*"::rest ->
    let (primUitdr, rest2) = splits_primaire_uitdrukking_van_tokens rest in
    splits_mult_uitdrukking_rest_van_tokens (ProductUitdrukking (uitdr, primUitdr)) rest2
  | "/"::rest ->
    let (primUitdr, rest2) = splits_primaire_uitdrukking_van_tokens rest in
    splits_mult_uitdrukking_rest_van_tokens (QuotientUitdrukking (uitdr, primUitdr)) rest2
  | _ ->
    (uitdr, tokens)
and splits_primaire_uitdrukking_van_tokens tokens =
  match tokens with
    "("::rest ->
    let (uitdr, rest2) = splits_uitdrukking_van_tokens rest in
    let ")"::rest3 = rest2 in
    (uitdr, rest3)
  | getal::rest ->
    let waarde = int_of_string getal in
    (GetalUitdrukking waarde, rest)

let uitdrukking_van tekst =
  let (uitdr, []) = splits_uitdrukking_van_tokens (tokens_van tekst) in
  uitdr