From: Jacques Garrigue <garrigue@kurims.kyoto-u.ac.jp>
To: alex@baretta.com
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] Again on pattern matching and strings
Date: Thu, 24 Oct 2002 17:01:23 +0900 [thread overview]
Message-ID: <20021024170123O.garrigue@kurims.kyoto-u.ac.jp> (raw)
In-Reply-To: <3DB79CD7.6040600@baretta.com>
From: Alessandro Baretta <alex@baretta.com>
> Stefano Zacchiroli wrote:
> > What about:
> >
> > | Some m when m = printer_set_unit -> ...
> > | Some m when m = printer-reset -> ...
> > | Some m when m = printer_formfeed -> ...
> > ...
> > | Some (_) -> assert false
> > | None -> ()
> >
> > It isn't so bad ...
>
> Eh, no! This is really unacceptable as a general solution.
> Of course, I could have coded my function this way, but this
> technique is not scalable, especially from the perspective
> of computational efficiency. Your code is compiled as a
> sequence of comparisons on a strings. Hence, the matched
> string is scanned once for every pattern. With constant
> patterns, on the other hand, the compiler should scan the
> string only once and jump to appropriate code. This is more
> compact, but not necessarily more efficient, as Jacques
> pointed out a while ago.
> ( http://caml.inria.fr/archives/200101/msg00111.html )
That message was about polymorphic variants, which are encoded as
integers, and for which pattern-matching is a decision tree.
However, if you look in bytecomp/matching.ml, you will see that string
patterns are just checked sequentially (the ordering is not used).
Moreover, the match compiler seems to be clever enough to compile
properly the above style:
# function Some s when s = a -> 0 | Some s when s = b -> 1
| Some s when s = c -> 2 | Some _ -> assert false | None -> 3;;
(let
(a/64 (apply (field 0 (global Toploop!)) "a")
b/65 (apply (field 0 (global Toploop!)) "b")
c/66 (apply (field 0 (global Toploop!)) "c"))
(function param/73
(if param/73
(let (s/70 (field 0 param/73))
(if (string_equal s/70 a/64) 0
(if (string_equal s/70 b/65) 1
(if (string_equal s/70 c/66) 2
(raise
(makeblock 0 (global Assert_failure/26g) [0: "" 94 106]))))))
3)))
- : string option -> int = <fun>
So efficiency is actually not a reason to avoid this style...
(Verbosity may be one.)
Jacques Garrigue
-------------------
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
next prev parent reply other threads:[~2002-10-24 8:01 UTC|newest]
Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top
2002-10-23 23:47 Alessandro Baretta
2002-10-23 23:46 ` Alexander V.Voinov
2002-10-23 23:57 ` Stefano Zacchiroli
2002-10-24 7:10 ` Alessandro Baretta
2002-10-24 7:38 ` Stefano Zacchiroli
2002-10-24 8:01 ` Jacques Garrigue [this message]
2002-10-24 12:38 ` Alessandro Baretta
2002-10-24 13:24 ` Luc Maranget
2002-10-24 15:13 ` Alessandro Baretta
2002-10-24 16:26 ` Sven Luther
2002-10-25 8:40 ` Luc Maranget
2002-10-24 4:11 ` Christopher Quinn
[not found] ` <15799.14325.887770.501722@karryall.dnsalias.org>
2002-10-24 7:43 ` Alessandro Baretta
2002-10-24 8:51 ` Daniel de Rauglaudre
2002-10-24 9:50 ` Stefano Zacchiroli
2002-10-24 10:30 ` Noel Welsh
2002-10-24 12:59 ` Daniel de Rauglaudre
2002-10-24 13:16 ` Basile STARYNKEVITCH
2002-10-25 10:29 ` Daniel de Rauglaudre
2002-10-24 12:34 ` Alessandro Baretta
2002-10-24 12:51 ` Daniel de Rauglaudre
[not found] <IIEMJEMIMDMLIIPHPOBLOELNCAAA.fsmith@mathworks.com>
2002-10-24 7:16 ` Alessandro Baretta
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=20021024170123O.garrigue@kurims.kyoto-u.ac.jp \
--to=garrigue@kurims.kyoto-u.ac.jp \
--cc=alex@baretta.com \
--cc=caml-list@inria.fr \
/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