"ocaml_beginners"::[] what is this control structure called?

Suppose I have a function that returns an option type. I want to
apply f to each item in a list until I find a non-None result, then
return that underlying value. The code is simple:

let rec find_some f = function
| x :: rest -> (match f x with Some y -> y | None -> find_some f rest)
| [] -> raise Not_found

Is there a commonly-used name for this in the FP world?

--
Eric Cooper e c c c m u . e d u

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

.

On 3-Mar-08, at 10:20 AM, Eric Cooper wrote:

> Suppose I have a function that returns an option type. I want to
> apply f to each item in a list until I find a non-None result, then
>; return that underlying value. The code is simple:
>
> let rec find_some f = function
> | x :: rest -> (match f x with Some y -> y | None -> find_some f rest)
> | [] -> raise Not_found
>
> Is there a commonly-used name for this in the FP world?
>

A search?

OK, that wasn't funny.

-Mike

>
>
> --
> Eric Cooper e c c c m u . e d u
>
>

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

.

> Suppose I have a function that returns an option type. I want to
> apply f to each item in a list until I find a non-None result, then
>; return that underlying value. The code is simple:
>
> let rec find_some f = function
> | x :: rest -> (match f x with Some y -> y | None -> find_some f rest)
> | [] -> raise Not_found

The following implementation is tail-recursive. Additionally, it moves
more information about the function's behavior into the function's
signature. I changed its name to something that sounds more
appropriate to me.

let rec find_first f = function
| x :: rest -> (match f x with Some y -> Some y | None -> find_some f rest)
| [] -> None

> Is there a commonly-used name for this in the FP world?

I would check Hoogle for functions with the signature ((a -> Maybe b)
-> [a] -> Maybe b) to see if someone else has done something similar.

--

I like to find simple solutions to overlooked problems that actually
need to be solved, and deliver them as informally as possible,
starting with a very crude version 1, then iterating rapidly.

- Paul Graham, Six Principles for Making New Things -

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

.

Zitat von Eric Cooper < ecc%40cmu.edu">ecccmu.edu&gt;:

&gt; Suppose I have a function that returns an option type. I want to
> apply f to each item in a list until I find a non-None result, then
>; return that underlying value. The code is simple:
>
> let rec find_some f = function
> | x :: rest -> (match f x with Some y -> y | None -> find_some f
> rest)
&gt; | [] -> raise Not_found
>
&gt; Is there a commonly-used name for this in the FP world?
[...]

What is it that you are looking for it's name?
The functionality that the function provides?
or the way the function is programmed?

For the first one:
------------------

You have a serarch on a list with a higher-order function f,
that gives back a result on the list elements with type o'b option.

So, the name would be "lookup" or "search"...?!
But it stops at the first found element.

It's a kind of parameterized (with a higher-order function)
association-list search.

For the second one:
-------------------

If you mean the way, the function is build,
I would say: it's a recursive function that uses a pattern-match.

Example usage of the function:
==============================

******************************************
oliversiouxsie2:~$ ledit ocaml
Objective Caml version 3.09.2

# let rec find_some f = function
| x :: rest -> (match f x with Some y -> y | None -> find_some f rest)
| [] -> raise Not_found ;;
val find_some : ('a -> 'b option) -> 'a list -> 'b = <fun>;
# find_some (fun x -> x) [None;None;None];;
Exception: Not_found.
# find_some (fun x -> x) [None; Some 4 ; None];;
- : int = 4
# let li = [2;55;6;4;5;7;3;76;2;66];;
val li : int list = [2; 55; 6; 4; 5; 7; 3; 76; 2; 66]
# find_some (fun x -> if x * x < 100 then Some x else None) li;;
- : int = 2
# find_some ( fun x -> if x * x > 100 then Some x else None) li;;
- : int = 55

******************************************

Ciao,
Oliver

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

.

As others have pointed out, from a certain point of view you're
searching on the predicate then projecting down to the base type:
let find_some f lst =
let x = List.find (fun x -> match f x with Some _ -> true | _ ->
false) lst in
let yopt = f x in
match yopt with
| Some y -> y
| _ -> assert false

>From another point of view, you're mapping a partial function over a
list and then selecting an aribtrary element (i.e., the first).
Standard ML has a function map_partial that does this directly:
let find_some f lst = List.hd (map_partial f lst)

Haskell has a similar function called mapMaybe (Maybe a in Haskell is
equivalent to 'a option in OCaml). Note that, with laziness, the above
is no less efficient than your version.

Chris

On Mon, Mar 3, 2008 at 10:20 AM, Eric Cooper < ecc%40cmu.edu">ecccmu.edu&gt; wrote:
&gt; Suppose I have a function that returns an option type. I want to
> apply f to each item in a list until I find a non-None result, then
>; return that underlying value. The code is simple:
>
> let rec find_some f = function
> | x :: rest -> (match f x with Some y -> y | None -> find_some f rest)
&gt; | [] -> raise Not_found
>
&gt; Is there a commonly-used name for this in the FP world?
&gt;
> --
> Eric Cooper e c c c m u . e d u
>
>
>; Archives up to November 11, 2006 are also downloadable at http://www.connettivo.net/cntprojects/ocaml_beginners/
> The archives of the very official ocaml list (the seniors' one) can be found at http://caml.inria.fr
> Attachments are banned and you're asked to be polite, avoid flames etc.
>; Yahoo! Groups Links
&gt;
>
>
>;
>

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

.

Zitat von Oliver Bandel < oliver%40first.in-berlin.de">oliverfirst.in-berlin.de>:

[...]
>; You have a serarch on a list with a higher-order function f,
> that gives back a result on the list elements with type o'b option.

The function find_some is the HOF, not f.

Too tired....

Ciao,
Oliver

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

.

> >> let rec find_some f = function
> >> | x :: rest -> (match f x with Some y -> y | None -> find_some f rest)
&gt; >> | [] -> raise Not_found
> >
>; > The following implementation is tail-recursive.
>;
> The above implementation was tail-recursive too.
>;
> [...]
&gt; > let rec find_first f = function
> > | x :: rest -> (match f x with Some y -> Some y | None -> find_some f rest)
&gt; > | [] -> None
>; >

I was under the impression that the tail-recursion optimization could
not be applied to a function that might throw an exception because
debugging information would be lost (tail-recursion changes the stack
trace). If I am wrong about this, I would love to hear it.

--

I like to find simple solutions to overlooked problems that actually
need to be solved, and deliver them as informally as possible,
starting with a very crude version 1, then iterating rapidly.

- Paul Graham, Six Principles for Making New Things -

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

.

On Tue, 4 Mar 2008, Eric Lavigne wrote:

>> >> let rec find_some f = function
>> >> | x :: rest -> (match f x with Some y -> y | None -> find_some f rest)
&gt;> >> | [] -> raise Not_found
>> >
>;> > The following implementation is tail-recursive.
>;>
>;> The above implementation was tail-recursive too.
>;>
>;> [...]
&gt;> > let rec find_first f = function
>> > | x :: rest -> (match f x with Some y -> Some y | None -> find_some f rest)
&gt;> > | [] -> None
>;> >
>;
> I was under the impression that the tail-recursion optimization could
&gt; not be applied to a function that might throw an exception because
> debugging information would be lost (tail-recursion changes the stack
&gt; trace). If I am wrong about this, I would love to hear it.

Basically any function could throw an exception (Stack_overflow,
Sys.Break, ...).

I think you're confusing with try...with blocks. The following
function causes a stack overflow when called:

let rec f () = try f () with Exit -> ()

The following loops forever:

let rec f () = if Random.int 1 = 2 then raise Exit else f ();;

Martin

--
http://wink.com/profile/mjambon
http://martin.jambon.free.fr

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

.

On Tuesday 04 March 2008 13:24:41 Eric Lavigne wrote:
&gt; > >> let rec find_some f = function
> > >>
> > >> | x :: rest -> (match f x with Some y -> y | None -> find_some f
> > >> | rest) [] -> raise Not_found
> > >
>; > > The following implementation is tail-recursive.
>; >
>; > The above implementation was tail-recursive too.
>; >
>; > [...]
&gt; >
>; > > let rec find_first f = function
> > >
>; > > | x :: rest -> (match f x with Some y -> Some y | None -> find_some f
> > > | rest) [] -> None
>;
> I was under the impression that the tail-recursion optimization could
&gt; not be applied to a function that might throw an exception because
> debugging information would be lost (tail-recursion changes the stack
&gt; trace). If I am wrong about this, I would love to hear it.

What you're referring to only applies to functions that handle exceptions
using "try&quot; blocks. Specifically, exception handlers must be pushed onto the
stack so they obviate any tail-like calls between the "try&quot; and the "with".

Raising exceptions is fine: it does not undermine tail calls.

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

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

.

> > I was under the impression that the tail-recursion optimization could
&gt; > not be applied to a function that might throw an exception because
> > debugging information would be lost (tail-recursion changes the stack
&gt; > trace). If I am wrong about this, I would love to hear it.
>
> What you're referring to only applies to functions that handle exceptions
> using "try&quot; blocks. Specifically, exception handlers must be pushed onto the
> stack so they obviate any tail-like calls between the "try&quot; and the "with".
&gt;
> Raising exceptions is fine: it does not undermine tail calls.

So if I place a "try ... with" at the top of my application, as in the
following pseudo-application, tail-recursion is turned off for the
entire application? Ouch. My previous (mis)understanding of the
situation was much more pleasant. Now the performance of my function
depends on the context in which the function is used.

try
run_my_application ()
with
Stack_overflow -> print_endline "Functional programming and error
handling don't mix as well as I thought.&quot;

--

I like to find simple solutions to overlooked problems that actually
need to be solved, and deliver them as informally as possible,
starting with a very crude version 1, then iterating rapidly.

- Paul Graham, Six Principles for Making New Things -

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

.