"ocaml_beginners"::[] mutual recursion

I noticed the tutorial page
http://www.ocaml-tutorial.org/labels/discussion was asking for a
simple, real-world example of mutual recursion. I just wrote this in
my dawg library:

(* Remove a letter from a bag. If the letter doesn't exist, try
removing a blank *)
let bag_play letter bag =
try bag_remove letter bag
with Not_found -> bag_remove '.' bag;;

(* find all anagrams in a given bag *)
let rec anagrams bag path =
List.flatten (mapsibs (follow_if bag) path)
and follow_if bag path =
try
let new_bag = bag_play (letter path.node) bag in
if new_bag = Bag.empty then word_of path
else anagrams new_bag (step path)
with Not_found -> [] | No_ptr -> []
;;

A path is a prefix string and a node, mapsibs maps over all possible
single-letter extensions to a path (i.e. keeping the prefix constant
and running down the list of the current node's siblings), and step
extends the prefix by one letter and moves the node pointer to that
letter's subtrie.

Not sure if this would count as a non-trivial example, since the
follow_if function can easily be inlined into an anonymous function,
but then, that can be said for a lot of other examples. It's
definitely a case where the code looks cleaner expressed using mutual
recursion than it would any other way.

And while I'm on the topic, is there any difference, in terms of the
compiled code, between

let rec foo
let bar = [....] in
[ .. body of foo .. ]

and

let rec foo
[ .. body of foo .. ]
and bar = [....]

I tend to prefer the latter style (I miss "where" from Haskell!) but
if there's a performance penalty I'll know to avoid it in time- or
space-critical functions.

martin

martin

Messages in this topic (1) Reply (via web post) | Start a new topic

.

On Wed, Dec 13, 2006 at 04:36:23AM +0530, Martin DeMello wrote:
> And while I'm on the topic, is there any difference, in terms of the
> compiled code, between
>
> let rec foo
> let bar = [....] in
> [ .. body of foo .. ]
>
> and
>
> let rec foo
> [ .. body of foo .. ]
> and bar = [....]
>
> I tend to prefer the latter style (I miss "where" from Haskell!) but
> if there's a performance penalty I'll know to avoid it in time- or
> space-critical functions.

I wouldn't worry too much about the optimisation issue. The bigger
story is that the second form makes the 'bar' symbol visible outside
'foo', which may or may not be what you want.

I agree that 'where' in Haskell is nice. It should be possible to
implement something in camlp4.

Rich.

--
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Internet Marketing and AdWords courses - http://merjis.com/courses - NEW!
Merjis blog - http://blog.merjis.com - NEW!

Messages in this topic (2) Reply (via web post) | Start a new topic

.

Shalom, Richard.

RJ> I agree that 'where' in Haskell is nice. It should be possible to
RJ> implement something in camlp4.

There already exists "where", but in revised syntax.
Very nice to write something like this:

...
let ...
in
some_long_function args
where [rec] some_long_function args =
...
;

It's easy to read: in the beginning we see let-bindings that
create "environment" for some_long_function, then we see call
to function, and then the function itself.
And it's possible to do some more:

...
let ...
in do
{ let res = some_long_function args
in
do_something_with res
}
where [rec] some_long_function args =
...
;

But guys who use original syntax really have to implement
"where" using camlp4.

--
WBR,
dmitry mailto: gds-mlsts%40moldavcable.com">gds-mlstsmoldavcable.com

Messages in this topic (3) Reply (via web post) | Start a new topic

.

On Tuesday 12 December 2006 23:06, Martin DeMello wrote:
> Not sure if this would count as a non-trivial example, since the
> follow_if function can easily be inlined into an anonymous function,
> but then, that can be said for a lot of other examples. It's
> definitely a case where the code looks cleaner expressed using mutual
> recursion than it would any other way.

I think you can always rephrase mutual recursion in other terms. For example,
by making the functions higher-order and passing in the next function for
them to branch to.

Consider splitting a list into its even- and odd-indexed elements:

# let rec even es os = function
| [] -> es, os
| e::t -> odd (e::es) os t
and odd es os = function
| [] -> es, os
| o::t -> even es (o::os) t;;
val even : 'a list -> 'a list -> 'a list -> 'a list * 'a list = <fun>;
val odd : 'a list -> 'a list -> 'a list -> 'a list * 'a list = <fun>;

For example:

# even [] [] [0;1;2;3;4;5];;
- : int list * int list = ([4; 2; 0], [5; 3; 1])

There are many other ways to write this. You can write the even function in
one go, of course, but then you lose the "odd&quot; function:

# let rec even a b = function
| [] -> a, b
| [h] -> h::a, b
| h1::h2::t -> even (h1::a) (h2::b) t;;
val even : 'a list -> 'a list -> 'a list -> 'a list * 'a list = <fun>;

Or you can write the even and odd functions separately, as higher-order
functions that accept odd or even respectively (this is known as "untying the
knot&quot;):

# let rec even odd es os = function
| [] -> es, os
| e::t -> odd even (e::es) os t;;
val even :
('a -> 'b list -> 'c -> 'b list -> 'b list * 'c) ->
'b list -> 'c -> 'b list -> 'b list * 'c as 'a = <fun>;

# let rec odd even es os = function
| [] -> es, os
| o::t -> even odd es (o::os) t;;
val odd :
('a -> 'b -> 'c list -> 'c list -> 'b * 'c list) ->
'b -> 'c list -> 'c list -> 'b * 'c list as 'a = <fun>;

Note that this solution needs recursive types to be enabled with -rectypes.

Yet another alternative is to use a variant or polymorphic variant to evade
the need for -rectypes:

# let rec even (`F odd) es os = function
| [] -> es, os
| e::t -> odd even (e::es) os t;;
val even :
[< `F of 'a -> 'b list -> 'c -> 'b list -> 'b list * 'c ] ->
'b list -> 'c -> 'b list -> 'b list * 'c as 'a = <fun>;

or:

# type 'a f =
F of ('a f -> 'a list -> 'a list -> 'a list -> 'a list * 'a list);;

# let rec even (F odd) es os = function
| [] -> es, os
| e::t -> odd even (e::es) os t;;
val even :
'a f -> 'a list -> 'a list -> 'a list -> 'a list * 'a list = <fun>;

So mutual recursion is the most elegant way to present both "even" and "odd&quot;
functions to the user.

&gt; And while I'm on the topic, is there any difference, in terms of the
> compiled code, between
&gt;
> let rec foo
> let bar = [....] in
> [ .. body of foo .. ]
>
&gt; and
>
> let rec foo
> [ .. body of foo .. ]
> and bar = [....]
&gt;
> I tend to prefer the latter style (I miss "where" from Haskell!) but
> if there's a performance penalty I'll know to avoid it in time- or
> space-critical functions.

Provided they are equivalent I think performance will be equal. However, with
the former it is easy to "accidentally&quot; capture some external variables and
force the generation of a closure. Closures are slower to invoke than
non-closure functions, so this can affect performance.

In general, I'd advise people to pollute the namespace with blah_aux functions
instead, as the stdlib does.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Messages in this topic (4) Reply (via web post) | Start a new topic

.

On Wed, 13 Dec 2006, dmitry grebeniuk wrote:

> Shalom, Richard.
>
> RJ> I agree that 'where' in Haskell is nice. It should be possible to
> RJ> implement something in camlp4.
&gt;
> There already exists "where", but in revised syntax.
&gt; Very nice to write something like this:
>;
> ...
> let ...
> in
> some_long_function args
> where [rec] some_long_function args =
> ...
> ;
>
&gt; It's easy to read: in the beginning we see let-bindings that
> create "environment&quot; for some_long_function, then we see call
> to function, and then the function itself.
&gt; And it's possible to do some more:
>;
> ...
> let ...
> in do
> { let res = some_long_function args
> in
> do_something_with res
> }
> where [rec] some_long_function args =
> ...
> ;
>
&gt; But guys who use original syntax really have to implement
> "where" using camlp4.

Personally, I am not fond of this syntax, because it doesn't mix well with
&quot;let in" which works the other way around. Maybe it's not that bad in real
code, but I have always thought that it is too easy to create unclear
situations like this one:

let x = 1 in
x + y
where x = 2 * y

Martin

--
Martin Jambon, PhD
http://martin.jambon.free.fr

Messages in this topic (5) Reply (via web post) | Start a new topic

.

Shalom, Martin.

MJ> Personally, I am not fond of this syntax, because it doesn't
MJ> mix well with "let in" which works the other way around. Maybe
MJ&gt; it's not that bad in real code, but I have always thought that
MJ&gt; it is too easy to create unclear situations like this one:
MJ&gt;
MJ> let x = 1 in
MJ> x + y
MJ> where x = 2 * y

Really, such situations are possible, but they are very rare in
real code, since "let in" and "where" bindings usually have different
names. I'm using "where" not too often, only when it simplifies
reading of code and does not introduce problems like the one you've
described.

--
WBR,
dmitry mailto: gds-mlsts%40moldavcable.com">gds-mlstsmoldavcable.com

Messages in this topic (6) Reply (via web post) | Start a new topic

.