From: Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr>
To: Mattia Dongili <dongili@supereva.it>
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] newbie nary tree problem
Date: Fri, 13 Jun 2003 12:41:37 +0200 [thread overview]
Message-ID: <16105.43617.135822.74686@gargle.gargle.HOWL> (raw)
In-Reply-To: <20030609222125.0c2cb1c8.dongili@supereva.it>
> Her comes my problem: I need to implement some kind of pattern matching
> in an nary tree structure with as follow
>
> type term = Const of int | Var of string | Term of string * term list;;
>
> type matchres = NoMatch | Subst of (string * term) list;;
>
> type matchres represent a substitution list in a successful pattern
> matching, I need to implement this pattern matching as follows:
>
> matchterm : term * term -> matchres = <fun>
I couldn't find out the precise meaning of your code, but if you want
to implement matching (that is *not* unification), here is a simple
way to do it:
======================================================================
module Subst = Map.Make(String)
exception NoMatch
let rec match_term s = function
| Const n1, Const n2 when n1 = n2 ->
s
| Var v1, t2 ->
(try if Subst.find v1 s = t2 then s else raise NoMatch
with Not_found -> Subst.add v1 t2 s)
| Term (f1, l1), Term (f2, l2) when f1 = f2 ->
match_terms s (l1, l2)
| _ ->
raise NoMatch
and match_terms s = function
| [], [] ->
s
| t1 :: l1, t2 :: l2 ->
match_terms (match_term s (t1, t2)) (l1, l2)
| _ ->
raise NoMatch
let matching t1 t2 = match_term Subst.empty (t1, t2)
======================================================================
Notice the use of an exception NoMatch instead of a sum type, and the
use of Ocaml's maps instead of association lists.
Hope this helps,
--
Jean-Christophe Filliâtre (http://www.lri.fr/~filliatr)
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
prev parent reply other threads:[~2003-06-13 10:51 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2003-06-09 20:21 Mattia Dongili
2003-06-13 10:41 ` Jean-Christophe Filliatre [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=16105.43617.135822.74686@gargle.gargle.HOWL \
--to=jean-christophe.filliatre@lri.fr \
--cc=caml-list@inria.fr \
--cc=dongili@supereva.it \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox