1{- 
2   Poly: limited polynomial arithmetic
3   
4  Part of Mackerel: a strawman device definition DSL for Barrelfish
5   
6  Copyright (c) 2007, 2008, ETH Zurich.
7  All rights reserved.
8  
9  This file is distributed under the terms in the attached LICENSE file.
10  If you do not find this file, copies can be found by writing to:
11  ETH Zurich D-INFK, Haldeneggsteig 4, CH-8092 Zurich. Attn: Systems Group.
12-}  
13
14module Poly where
15
16import Data.List
17
18reduce :: [ (Integer, [String]) ] -> [ (Integer, [String]) ]
19reduce p = [ (i, sort s) | (i,s) <- reduce1 (sort p), i /= 0 ]
20
21reduce1 :: [ (Integer, [String]) ] -> [ (Integer, [String]) ]
22reduce1 [] = []
23reduce1 [h] = [h]
24reduce1 ((i1, idlist1):(i2, idlist2):t)
25    | idlist1 == idlist2 = 
26        reduce1 ((i1+i2, idlist1):t)
27    | otherwise = 
28        (i1, idlist1):(reduce1 ((i2, idlist2):t))
29
30