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)

Lijsten van lijsten van lijsten van ... van lijsten van tekens

We kunnen een type van willekeurig diep genestelde lijsten van tekens (eigenlijk dus een type van bomen van tekens met vertakkingen (knopen) met willekeurig veel takken) definiëren als volgt:

type tekenboom =
  Blad of char
| Vertakking of tekenboom list

Een beknopte notatie hiervoor is (ab(cde)). Dit stelt de tekenboom Vertakking [Blad 'a'; Blad 'b'; Vertakking [Blad 'c'; Blad 'd'; Blad 'e']] voor.

Oefening:

• Definieer een functie splits_tekenboom_van_tekens die, gegeven een lijst van tekens die begint met een beknopte voorstelling van een tekenboom, een paar teruggeeft met de tekenboom en de lijst van de overblijvende tekens. Bijvoorbeeld: splits_tekenboom_van_tekens ['('; 'a'; 'b'; ')'; 'c'; 'd'] evalueert tot (Vertakking [Blad 'a'; Blad 'b'], ['c'; 'd']). Hint: definieer deze functie wederzijds recursief met een functie splits_tekenbomen_van_tekens die, gegeven een lijst van tekens die begint met een aantal beknopte voorstellingen van tekenbomen, gevolgd door een rechterhaakje, een paar teruggeeft met de lijst van deze tekenbomen en een lijst met de overblijvende tekens (zonder het rechterhaakje).

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

Oefening:

• Kijk na dat de functie uitdrukking_van correct werkt door hem uit te proberen op een aantal stukken tekst die uitdrukkingen voorstellen.

Variabelen

Oefening:

• Breid de definitie van het type uitdrukking uit met een constructor voor variabele-uitdrukkingen. Die constructor neemt als argument de naam (een stuk tekst) van een variabele. Breid ook de definitie van waarde_van uit zodat de functie werkt voor uitdrukkingen die variabelen vernoemen. De functie waarde_van zal als extra argument een associatielijst (zie Associatielijsten) moeten nemen die de variabelen associeert met hun waarde. Gebruik de functie zoek_op (zie Associatielijsten) om de waarde van een variabele op te zoeken in de associatielijst.