Tuesday, May 31, 2011

[qxfkkwhs] Syntactic fold

A common feature of many embedded domain specific languages and libraries in Haskell is to define an infix operator and chain together "objects" with it: foo `op` bar `op` baz `op` quux.

But this requires typing op over and over again, and having to repeat yourself suggests a flaw in the language.  Better would be a new language construct: (syntactic_foldl op foo bar baz quux).

Lists are not enough for everything (foo bar baz quux may be of different types), but linearity, things chained one after another, is fundamental and common.

(Tree structures structures are the next more complicated structure, but less trodden.)

Template Haskell?


Anonymous said...

For that to work in general, your type system would probably need to be turing complete. A non-turing complete type system is indeed a language flaw, as there will be computable patterns which cannot be abstracted over. A compiler that doesn't halt is also (arguably) a language flaw. Can't have it both ways :-)

(Well I guess you can -- you can decide which language flaw is more severe, and use or refuse to use Template Haskell, which could solve your problem easily)

Anonymous said...

It is true that foo, bar, baz and quux may have different types, but these types cannot vary too wildly. Consider the expression

foo `op` bar `op` baz

where op has the (preliminary) type a -> b -> c, where some of the types a, b and c may be equal.

Now, this expression can be interpreted either as

foo `op` (bar `op` baz)
(foo `op` bar) `op` baz

which means that the type c is equal to either a or b (i.e. op can have either the type a -> b -> a or a -> b -> b).

As a consequence, we get that in the chain of expressions

x1 `op` ... `op` xn

either x1, ..., xn-1 have the same type, or x2, ..., xn have the same type. Thus folding over these chains can be done with the usual foldr and foldl functions, as their types indicate:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldl :: (a -> b -> a) -> a -> [b] -> a

Ken said...

luqui: this is a purely syntactic transformation, so type-checking the syntactic fold is just as difficult as if the programmer had typed the infix form.

Anonymous: No. "op" may be polymorphic. The "classic" example is op = (.), and there is no way to do foldr (.) f [g,h,...].

The next famous example is op = (>>=), for which Haskell provides syntactic sugar "do" notation. My proposal, in a way, is a generalization of "do" notation for chaining operators beyond >>= .

Anonymous said...

Thristshandle some of what you want, but may still be too constrained.

Tyr said...

foo :: a -> [a -> a] -> a
foo x ys = foldl (.) id ys x

>foo 5 [(*2), (+1)]
12 :: Integer

>foo 5.0 [(*2), (+1)]
12.0 :: Double

You can do foldl (.) [f, g, h]

Anonymous said...

While it is true that you can do foldl (.) over a list it is not quite what we are looking for.

Prelude> :t foldl (.)
foldl (.) :: (a -> c) -> [a -> a] -> a -> c

You can see that this requires all the elements of the list to have same type (a->a).

// Aune

A better example of what he wants is :

show.(read ::String -> Double).show.(read ::String -> Int)

In this example the functions chained together are of different type and so we cant use the simple foldl (.) approach.

Axio said...

Well, basically, you just want macros à la lisp…

(define-macro (deal op . params)
`,(intersperce op params))
(deal op foo bar qux lol)

=> (foo op bar op qux op lol)

(well, you'd actually want a composition that gives valid code, so
(define-macro (deal2 op . params)
`,(fold-left (lambda (r x) `(,op ,r ,x)) (car params) (cdr params)))
(deal2 op foo bar qux lol)

=> (op (op (op foo bar) qux) lol)

So, you'll probably have to hack into the compiler/reader...

Anonymous said...

What you're looking for are "idiom brackets". There are a number of ways of implementing them, one of which is available on the hawiki. There's no need to invoke TH, just a little type-level hackery is all.

That this is what you need follows directly from the requirements. In particular, the requirement that each of the "arguments" be allowed to be of a different type, and yet that they can all be composed by "the same" operator. Since its the same operator, it's a monoidal operation (or at least semigoupal); and since it can chain with different types, it's the same generalization that turns groups into groupoids. That transformation also turns monoids into "monoidoids", aka categories. So, the infix operation is exactly (.) like you suggested--- just generalized to whatever category you're seeking syntax for. (Notably, (<=<) is just the (.) for the Kleisli category induced by a monad; so (>>=) is essentially the same thing.) Applicative functors are strong lax monoidal, which means they have the same sort of structure that you need to construct your category.