Hi Oleg,
at the possible risk of straying from Tom's original problem, consider
the following generator that could conceivably occur in practice:
> sklansky f [] = []
> sklansky f [x] = [x]
> sklansky f xs = left' ++ [ f (last left') r | r <- right' ]
> where
> (left, right) = splitAt (leng
On Feb 15, 2008, at 1:15 PM, Tony Finch wrote:
On Thu, 14 Feb 2008, [EMAIL PROTECTED] wrote:
As I understand the original problem had less to do with the number
of
comparison but more to do with the cost of a single comparison. In an
impure language, we can use constant-time physical equal
On Thu, 14 Feb 2008, [EMAIL PROTECTED] wrote:
>
> As I understand the original problem had less to do with the number of
> comparison but more to do with the cost of a single comparison. In an
> impure language, we can use constant-time physical equality. It is
> usually provided natively as pointe
Matthew Naylor wrote:
> it's not immediately clear (to me at least) how efficient your method
> will be in "practice". Any method based on common sub-expression
> elimination surely must inspect every node in the flattened graph. In
> the worst case, an acyclic graph containing n nodes could hav
On Feb 13, 2008 5:36 AM, Luke Palmer <[EMAIL PROTECTED]> wrote:
> On Feb 13, 2008 9:33 AM, <[EMAIL PROTECTED]> wrote:
> > The approach is based on the final tagless representation. Here is our
> > DSL:
> >
> > > class Exp repr where
> > >constant :: Int -> repr Int
> > >variable :: String
> tricky 0 = constant 0
> tricky d = add e0 e1
> where
> (e0, e1) = fork (tricky (d-1))
Oops, I just realised that this isn't a very good example of
expressible sharing! The problem is that it doesn't take any inputs,
and expressible sharing just collapses (partially evaluates) oper
Hello again,
since Oleg presented an approach to the sharing problem that works on
acyclic graphs, I may as well mention an alternative, pure, standard
Haskell solution which is to express the fork points in the circuit
(or expression), i.e. the points at which an expression is duplicated.
You nee
Hi Oleg,
it's not immediately clear (to me at least) how efficient your method
will be in "practice". Any method based on common sub-expression
elimination surely must inspect every node in the flattened graph. In
the worst case, an acyclic graph containing n nodes could have 2^n
nodes when flat
On Feb 13, 2008 9:33 AM, <[EMAIL PROTECTED]> wrote:
> The approach is based on the final tagless representation. Here is our
> DSL:
>
> > class Exp repr where
> >constant :: Int -> repr Int
> >variable :: String -> repr Int
> >add :: repr Int -> repr Int -> repr Int
> >sub :: repr
Tom Hawkins wrote:
] My DSLs invariably define a datatype to capture expressions; something
] like this:
]
] data Expression
] = Add Expression Expression
] | Sub Expression Expression
] | Variable String
] | Constant Int
] deriving Eq
] The problem comes when I want to generate efficie
10 matches
Mail list logo