summary |
shortlog |
changelog |
graph |
tags |
branches |
files |
changeset |
file |
revisions |
annotate |
diff |
raw

src/Pure/Concurrent/par_list.ML

author | wenzelm |

Tue Jul 21 20:37:31 2009 +0200 (2009-07-21) | |

changeset 32103 | ebdcff2b9810 |

parent 32094 | 89b9210c7506 |

child 32255 | d302f1c9e356 |

permissions | -rw-r--r-- |

map: subgroup of worker_group;

1 (* Title: Pure/Concurrent/par_list.ML

2 Author: Makarius

4 Parallel list combinators.

6 Notes:

8 * These combinators only make sense if the operator (function or

9 predicate) applied to the list of operands takes considerable

10 time. The overhead of scheduling is significantly higher than

11 just traversing the list of operands sequentially.

13 * The order of operator application is non-deterministic. Watch out

14 for operators that have side-effects or raise exceptions!

15 *)

17 signature PAR_LIST =

18 sig

19 val map: ('a -> 'b) -> 'a list -> 'b list

20 val get_some: ('a -> 'b option) -> 'a list -> 'b option

21 val find_some: ('a -> bool) -> 'a list -> 'a option

22 val exists: ('a -> bool) -> 'a list -> bool

23 val forall: ('a -> bool) -> 'a list -> bool

24 end;

26 structure Par_List: PAR_LIST =

27 struct

29 fun raw_map f xs =

30 if Future.enabled () then

31 let val group = Task_Queue.new_group (Future.worker_group ())

32 in Future.join_results (map (fn x => Future.fork_group group (fn () => f x)) xs) end

33 else map (Exn.capture f) xs;

35 fun map f xs = Exn.release_first (raw_map f xs);

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

46 | NONE => (Exn.release_first results; NONE))

47 end;

49 fun find_some P = get_some (fn x => if P x then SOME x else NONE);

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);

54 end;