Homomorphie-Sätze für Listen

  1. für jeden Hom exist. Zerlegung in map und reduce -- und das reduce kann man flexibel parallelisieren!

    Bsp: length = reduce (+) . map (const 1)

    map: parallel ausrechnen, reduce: balancierter Binärbaum.

  2. jeden Hom. kann man als foldl und als foldr schreiben

  3. (Umkehrung von 2.) Wenn eine Funktion sowohl als foldl als auch als foldr darstellbar ist, dann ist sie ein Hom. -- und kann (nach 1.) flexibel parallelisiert werden

    m.a.W: aus der Existenz zweier sequentieller Algorithmen folgt die Existenz eines parallelen Alg.



Johannes Waldmann 2013-06-18