author | wenzelm |
Wed, 01 Oct 2008 12:00:02 +0200 | |
changeset 28443 | de653f1ad78b |
parent 28383 | 3c5b4f636159 |
child 28549 | 78affc7d4d0f |
permissions | -rw-r--r-- |
28199 | 1 |
(* Title: Pure/Concurrent/par_list.ML |
2 |
ID: $Id$ |
|
3 |
Author: Makarius |
|
4 |
||
5 |
Parallel list combinators. |
|
6 |
||
7 |
Notes: |
|
8 |
||
9 |
* These combinators only make sense if the operator (function or |
|
10 |
predicate) applied to the list of operands takes considerable |
|
11 |
time. The overhead of scheduling is significantly higher than |
|
12 |
just traversing the list of operands sequentially. |
|
13 |
||
28358 | 14 |
* The order of operator application is non-deterministic. Watch out |
28199 | 15 |
for operators that have side-effects or raise exceptions! |
16 |
*) |
|
17 |
||
18 |
signature PAR_LIST = |
|
19 |
sig |
|
20 |
val map: ('a -> 'b) -> 'a list -> 'b list |
|
21 |
val get_some: ('a -> 'b option) -> 'a list -> 'b option |
|
22 |
val find_some: ('a -> bool) -> 'a list -> 'a option |
|
23 |
val exists: ('a -> bool) -> 'a list -> bool |
|
24 |
val forall: ('a -> bool) -> 'a list -> bool |
|
25 |
end; |
|
26 |
||
27 |
structure ParList: PAR_LIST = |
|
28 |
struct |
|
29 |
||
30 |
fun raw_map f xs = |
|
28304
4b0477452943
future tasks: support boolean priorities (true = high, false = low/irrelevant);
wenzelm
parents:
28199
diff
changeset
|
31 |
let val group = TaskQueue.new_group () in |
4b0477452943
future tasks: support boolean priorities (true = high, false = low/irrelevant);
wenzelm
parents:
28199
diff
changeset
|
32 |
Future.join_results (List.map (fn x => Future.future (SOME group) [] true (fn () => f x)) xs) |
4b0477452943
future tasks: support boolean priorities (true = high, false = low/irrelevant);
wenzelm
parents:
28199
diff
changeset
|
33 |
end; |
28199 | 34 |
|
28443 | 35 |
fun map f xs = Exn.release_first (raw_map f xs); |
28199 | 36 |
|
37 |
fun get_some f xs = |
|
38 |
let |
|
39 |
exception FOUND of 'b option; |
|
40 |
fun found (Exn.Exn (FOUND some)) = some |
|
41 |
| found _ = NONE; |
|
42 |
val results = raw_map (fn x => (case f x of NONE => () | some => raise FOUND some)) xs; |
|
43 |
in |
|
44 |
(case get_first found results of |
|
45 |
SOME y => SOME y |
|
28443 | 46 |
| NONE => (Exn.release_first results; NONE)) |
28199 | 47 |
end; |
48 |
||
49 |
fun find_some P = get_some (fn x => if P x then SOME x else NONE); |
|
50 |
||
51 |
fun exists P = is_some o get_some (fn x => if P x then SOME () else NONE); |
|
52 |
fun forall P = not o exists (not o P); |
|
53 |
||
54 |
end; |