-- |
-- Module      : Control.Parallel.TreeSearch
-- Copyright   : Fabian Reck, Sebastian Fischer
-- License     : PublicDomain
--
-- Maintainer  : Niels Bunkenburg (nbu@informatik.uni-kiel.de)
-- Stability   : experimental
-- Portability : portable
--
-- This Haskell library provides an implementation of parallel search
-- based on the search tree provided by the package tree-monad.
--
module Control.Parallel.TreeSearch ( parSearch ) where

import           Control.Monad.SearchTree
import           Control.Parallel

-- | Enumerate the leaves of a @SearchTree@ using parallel depth-first search.
parSearch :: SearchTree a  -- ^ tree to search
          -> [a]           -- ^ lazy list of leaves

parSearch :: SearchTree a -> [a]
parSearch SearchTree a
None = []
parSearch (One a
x) = [a
x]
parSearch (Choice SearchTree a
l SearchTree a
r) = [a]
rs [a] -> [a] -> [a]
forall a b. a -> b -> b
`par` (SearchTree a -> [a]
forall a. SearchTree a -> [a]
parSearch SearchTree a
l [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
rs)
 where
  rs :: [a]
rs = SearchTree a -> [a]
forall a. SearchTree a -> [a]
parSearch SearchTree a
r