src/Pure/Concurrent/par_list.ML
author wenzelm
Tue Jan 06 14:43:35 2009 +0100 (2009-01-06)
changeset 29368 503ce3f8f092
parent 29120 8a904ff43f28
child 32094 89b9210c7506
permissions -rw-r--r--
renamed structure ParList to Par_List;
     1 (*  Title:      Pure/Concurrent/par_list.ML
     2     Author:     Makarius
     3 
     4 Parallel list combinators.
     5 
     6 Notes:
     7 
     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.
    12 
    13   * The order of operator application is non-deterministic.  Watch out
    14     for operators that have side-effects or raise exceptions!
    15 *)
    16 
    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;
    25 
    26 structure Par_List: PAR_LIST =
    27 struct
    28 
    29 fun raw_map f xs =
    30   if Future.enabled () then
    31     let
    32       val group = Task_Queue.new_group ();
    33       val futures = map (fn x => Future.fork_group group (fn () => f x)) xs;
    34       val _ = List.app (ignore o Future.join_result) futures;
    35     in Future.join_results futures end
    36   else map (Exn.capture f) xs;
    37 
    38 fun map f xs = Exn.release_first (raw_map f xs);
    39 
    40 fun get_some f xs =
    41   let
    42     exception FOUND of 'b option;
    43     fun found (Exn.Exn (FOUND some)) = some
    44       | found _ = NONE;
    45     val results = raw_map (fn x => (case f x of NONE => () | some => raise FOUND some)) xs;
    46   in
    47     (case get_first found results of
    48       SOME y => SOME y
    49     | NONE => (Exn.release_first results; NONE))
    50   end;
    51 
    52 fun find_some P = get_some (fn x => if P x then SOME x else NONE);
    53 
    54 fun exists P = is_some o get_some (fn x => if P x then SOME () else NONE);
    55 fun forall P = not o exists (not o P);
    56 
    57 end;