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 (length xs
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 pointer
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
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 have 2^n
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
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 Int - repr Int -
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
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
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)
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 - repr Int
add
10 matches
Mail list logo
