"ocaml_beginners"::[] Pattern matching with guards (howto avoid repeating expensive operations?)

I've come across this a few times and, while I like pattern matching,
in this case it seems to be inefficient:

let rec get_clauses_without lit clauses = match clauses with
[] -> []
| h::t when ( List.length (remove_lit lit h) = 0 ) ->
get_clauses_without lit t
| h::t -> (remove_lit lit h) :: get_clauses_without lit t ;;

The problem here is with the remove_lit function being potentially
called twice and it can be an expensive operation, essentially it
removes the specified number (lit) from the list ( h in this case).
[clauses is a list of lists]

Is there any clean way to cache the result of the first remove_lit
call so that the result can be reused if the 2nd pattern doesn't match
and the third one does?

Something like the following (which isn't a valid Ocaml function):

let rec get_clauses_without lit clauses = match clauses with
[] -> []
| h::t when ( List.length (let x = ( remove_lit lit h)) = 0 ) ->
get_clauses_without lit t
| h::t -> (x) :: get_clauses_without lit t ;; (* reuse x from the
previous test *)

Phil

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

.

To partially answer my own question, this is probably preferrable:

(* this one is probably more efficient and thus preferrable *)
let rec get_clauses_without lit clauses = match clauses with
[] -> []
| h::t ->
let x = (get_clause_without lit h) in
if List.length x = 0 then
get_clauses_without lit t
else
x :: get_clauses_without lit t ;;

...so one probably wouldn't use guards in this situation, correct?

On 9/28/07, Phil Tomson < rubyfan%40gmail.com">rubyfangmail.com> wrote:
&gt;
>
>
&gt;
>
>
>; I've come across this a few times and, while I like pattern matching,
> in this case it seems to be inefficient:
>
> let rec get_clauses_without lit clauses = match clauses with
>; [] -> []
> | h::t when ( List.length (remove_lit lit h) = 0 ) ->
&gt; get_clauses_without lit t
> | h::t -> (remove_lit lit h) :: get_clauses_without lit t ;;
>
> The problem here is with the remove_lit function being potentially
> called twice and it can be an expensive operation, essentially it
> removes the specified number (lit) from the list ( h in this case).
&gt; [clauses is a list of lists]
&gt;
> Is there any clean way to cache the result of the first remove_lit
> call so that the result can be reused if the 2nd pattern doesn't match
&gt; and the third one does?
&gt;
> Something like the following (which isn't a valid Ocaml function):
>
&gt; let rec get_clauses_without lit clauses = match clauses with
>; [] -> []
> | h::t when ( List.length (let x = ( remove_lit lit h)) = 0 ) ->
&gt; get_clauses_without lit t
> | h::t -> (x) :: get_clauses_without lit t ;; (* reuse x from the
> previous test *)
>
> Phil
>;

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

.

You've already answered your own question correctly but here are some
interesting asides:

On Saturday 29 September 2007 02:07:37 Phil Tomson wrote:
&gt; To partially answer my own question, this is probably preferrable:
>
> (* this one is probably more efficient and thus preferrable *)
> let rec get_clauses_without lit clauses = match clauses with
>; [] -> []
>
> | h::t ->
&gt;
> let x = (get_clause_without lit h) in
> if List.length x = 0 then

This is a bad idea because List.length is T(n). Use:

match get_clause_without lit h with
| [] -> get_clauses_without lit t
| x -> x :: get_clauses_without lit t

>; get_clauses_without lit t
> else
>; x :: get_clauses_without lit t ;;
>
> ...so one probably wouldn't use guards in this situation, correct?

Yes. If you must use guards, you might consider laziness:

let p = lazy (remove_lit lit h) in
| h::t when Lazy.force p = [] -> get_clauses_without lit t
| h::t -> Lazy.force p :: get_clauses_without lit t ;;

You might also consider factoring out:

let cons_nonempty xs xss = match xs with
| [] -> xss
| xs -> xs:ss

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e

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

.

On 9/28/07, Jon Harrop < jon%40ffconsultancy.com">jonffconsultancy.com&gt; wrote:
&gt;
>
>
&gt;
>
>
>;
> >
>; > (* this one is probably more efficient and thus preferrable *)
> > let rec get_clauses_without lit clauses = match clauses with
>; > [] -> []
> >
>; > | h::t ->
&gt; >
>; > let x = (get_clause_without lit h) in
> > if List.length x = 0 then
>;
> This is a bad idea because List.length is T(n). Use:
>;
> match get_clause_without lit h with
>; | [] -> get_clauses_without lit t
> | x -> x :: get_clauses_without lit t

this was a pleasant "aha&quot; as i didn't realize you could nest these matches...
So now I have:

let rec get_clauses_without lit clauses = match clauses with
[] -> []
| h::t ->
match (get_clause_without lit h) with
[] -> get_clauses_without lit t
| x -> x :: get_clauses_without lit t ;;

...but in reality, wouldn't the empty list match [] take the same time
as List.length list = 0 ? There doesn't seem to be a List.empty
function for List, so maybe not.
I guess I would have thought that the list length would be stored in
the List data structure and would be incremented/decremented as things
were added/subtracted from the list and thus could be accessed in
constant time (?) but from what you're saying the list must be walked
to determine it's length.

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

.

On Tue, 2 Oct 2007 12:44:14 -0700, Phil Tomson wrote

> this was a pleasant "aha&quot; as i didn't realize you could nest these
matches...
> So now I have:
&gt;
> let rec get_clauses_without lit clauses = match clauses with
>; [] -> []
> | h::t ->
&gt; match (get_clause_without lit h) with
>; [] -> get_clauses_without lit t
> | x -> x :: get_clauses_without lit t ;;
>

> ...but in reality, wouldn't the empty list match [] take the same
> time as List.length list = 0 ?

There's an extra function call/return with List.length, which is
negligible. The problem, however comes if list is not empty, as you have to
march all the way through it to get the length.

> There doesn't seem to be a List.empty function for List, so maybe not.

If you want one, define your own:
let list_empty = function [] -> true | _ -> false

But the nested match is the equivalent of doing that definition and then
inlining it.

> I guess I would have
> thought that the list length would be stored in the List data
> structure and would be incremented/decremented as things were
> added/subtracted from the list and thus could be accessed in
> constant time (?) but from what you're saying the list must be
> walked to determine it's length.

Correct. length is stored for strings and arrays, but not lists.

One other thing to note is that you probably want to wrap your nested
matches in begin ... end (or (...) ) -- it painlessly removes a class of
bugs for the table if you do so.

--

William D. Neumann

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

.

On Tuesday 02 October 2007 20:44:14 Phil Tomson wrote:
&gt; I guess I would have thought that the list length would be stored in
> the List data structure and would be incremented/decremented as things
&gt; were added/subtracted from the list and thus could be accessed in
> constant time (?) but from what you're saying the list must be walked
&gt; to determine it's length.

Exactly. The built in data structures are light weight so they consume minimal
memory and you can augment them with such functionality as you wish. The
reason is simply that OCaml is optimized for handling large numbers of short
lists because this usage is common in functional programming.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e

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

.