[Haskell-cafe] "Rewrite thunk action" rule?

Luke Palmer lrpalmer at gmail.com
Sun Dec 21 13:10:15 EST 2008

On Sun, Dec 21, 2008 at 10:27 AM, Peter Todd <pete at petertodd.org> wrote:

> data Element = Element {
>    elementOrigin :: V,
>    elementSubs :: [Element]
>    }
>     | ElementThunk T Element
> transform :: T -> Element -> Element
> transform t (ElementThunk t2 e) = ElementThunk (tmul t t2) e
> transform t e = ElementThunk t e
> transform t e = Element {
>                    elementOrigin = tmulv t (elementOrigin e),
>                    elementSubs = map (transform t) (elementSubs e)
>                    }
> This gives a behavior close to what I want, applying a transform to an
> element results in a "thunk", and subsequent transforms simply modify
> the thunk, the problem is that I don't see a way to implicitly coerce an
> ElementThunk into an Element on demand for all the other code in the
> program that expects elements. (such as the elementOrigin function)

Oh!  Okay, studying your code a bit, I think I finally understand what
you're trying to do.  Tell me if I'm wrong.  You have a list of elements es
and a composition of transforms t1,t2,t3, and instead of applying t1, t2,
and t3 to each element, you want to collapse them together into a single
matrix and apply that matrix to each element.

This is definitely a modeling level thing to do; you don't need to go
anywhere near rewrite rules or thinking about internal representations or
anything like that.  A bit of old fashioned abstraction should do the trick.

Your Thunk representation is not that bad.  I can't really weigh the
trade-offs for you.  Keep the data type abstract and only allow access
through functions (like elementOrigin).  Then I don't see the problem with
redefining elementOrigin as:

elementOrigin (Element v subs) = v
elementOrigin (ElementThunk t e) = tmulv t (elementOrigin e)

Keep the number of operations which need to know the representation
(constructors) of Element as small as you can.

Another possibility is this:

data Element = Element
  { elementOrigin :: V
  , elementSubs :: [(T,Element)]

Where, of course, the transform for each sub-element is relative.

Overall I think your "thunk" solution is a very nice trade-off.  (Minor
rhetorical note: I would probably name your ElementThunk constructor
Transform or ElementTransform instead)

Hmm, you have an invariant that the pattern ElementThunk t (ElementThunk t
e) never occurs.  It would be good style to encode this:

data PrimElement = PrimElement { elementOrigin :: V, elementSubs ::
[Element] }
data Element = Element (Maybe T) PrimElement

That Maybe bugs me.  You could factor that out into the T type with a
special optimization for the identity transform.  Hmm, then the
[(T,Element)] encoding and this one are identical.  Fun. :-)

Short answer:  *abstract data type!*


> > By the way, this is very operational thinking for Haskell.  Haskell tries
> > quite hard to abstract away operational thinking, so thinking on this
> level
> > will be difficult and more work than you should be doing to write a
> program.
> Yes, but this part of the program is library code, that will be used by
> a whole pile of other stuff, so if I can get the right behavior
> "magically" the rest of the program will be a lot easier to write.
> FWIW this is EDA software, those "elements" refer to elements of a
> printed circuit board layout, and the transform operations correspond to
> stuff like moving a chip on the board. The representation of a simple IC
> would consist of something like an element, with a bunch of sub-elements
> for each pin, all of which have geometry data.
> > May I ask why you want this behavior?  Have you just tested it and
> observed
> > that it is running too slowly and you are trying to speed it up?
> I've written a previous version of this program in Python actually,
> where I explicitly modeled the lazy evaluation behavior that I wanted.
> It all worked great, but the overall speed was still quite slow.  I was
> hoping that Haskell, built around lazy evaluation already, would be a
> better fit.
> That, and in any case, other aspects of the program that I've re-written
> in Haskell saw about a 5-1 redunction in code length... :)
> --
> http://petertodd.org 'peter'[:-1]@petertodd.org
> Version: GnuPG v1.4.6 (GNU/Linux)
> iD8DBQFJTnx03bMhDbI9xWQRAhWvAJoD8JeQg/3Q3Oy5FNEAaVjbNDbg3QCfe5jJ
> Ob2IGxR4YDfiVpoTeOFcnBM=
> =RS6B
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20081221/7c14586b/attachment.htm

More information about the Haskell-Cafe mailing list