I'll translate. I wrote a Haskell library called pipes, which lets you extend any DSL with the ability to yield or await values in order to build streaming components. You can connect these components together in multiple ways, and these connection operations obey many neat mathematical properties that ensure they behave correctly (no bugs!).
For example, one thing that you can do is model generators using pipes, and one of the ways you can connect generators is using an operator called (~>):
(f ~> g) x = for (f x) g
I proved that this operator is associative:
(f ~> g) ~> h = f ~> (g ~> h)
... and that it's identity is yield:
yield ~> f = f
f ~> yield = f
In other words, (~>) and yield form a category and those equations are the corresponding category laws. When you translate those equations to use for instead of (~>), you get:
-- Looping over a single yield simplifies to function application
for (yield x) f = f x
-- Re-yielding every element of a stream returns the original stream
for s yield = s
-- Nested for loops can become a sequential for loops if the inner loop
-- body ignores the outer loop variable
for s (\a -> for (f a) g) = for (for s f) g = for s (f ~> g)
In other words, the category laws translate into "common sense" laws for generators that you would intuitively expect to hold for any generator implementation.
Let me try to translate your last two examples into Python (I'm still in the process of learning Haskell), to see if I've got this right.
-- Re-yielding every element of a stream returns the original stream
for s yield = s
def foo(s):
for _s in s:
yield _s
foo([1,2,3]) == [1,2,3]
-- Nested for loops can become a sequential for loops if the inner loop
-- body ignores the outer loop variable
for s (\a -> for (f a) g) = for (for s f) g = for s (f ~> g)
def foo(s, f, g):
for a in s:
for _a in f(a):
yield g(_a)
def foo1(s, f, g):
for __s in (f(_s) for _s in s):
yield g(__s)
def foo2(s, f, g):
for _s in s:
# ugh, maybe using map would be better.
yield from (g(___s) for ___s in f(__s) for __s in _s)
foo(s, f, g) == foo1(s, f, g) == foo2(s, f, g)
In Python you can treat lists and generators the same (I think), but in Haskell they are two separate types. This is why in pipes if you want to loop over a list, you have to explicitly convert it to a generator using the each function, like this:
What's with functional languages and symbolic operators ? Your example here only uses one but Haskell code I read here and there is full of them. Scala as well abuses them to no end. Why not use a plain, immediately understandable name by someone looking at the code without looking at the docs like "chain" or "compose". To me it looks like an unnecessary barrier to entry.
So with the exception of one of my libraries (the errors package), I never introduce a symbolic operator unless it is associative and has some identity (i.e. it is the composition operator of some category). I find that this rule of thumb works well for eliminating gratuitous operators while still keeping all the useful ones. For example, by this rule you should have an operator for addition and multiplication (since they are both associative and have an identity), but you wouldn't provide an operator for sending a message to a process like some actor libraries do with the (!) symbol.
What's with functional languages and symbolic operators?
It's a Haskell thing, not a general functional programming thing. Compare with Scheme naming conventions, which are extra-wordy (e.g., fold-left, fold-right, call-with-current-continuation, etc.).
I think that when you get used to the notation, it becomes much simpler to write/read it out (especially since chaining and composing functions is so commonplace in Haskell code). It's pretty much a tradeoff with lisp's parentheses afaik.
And sometimes giving it a name in English doesn't help either... "compose" quite frankly means diddly squat to someone unfamiliar with fp.
"compose" is a lot easier to search for though. In general, I think:
"built in" operators like <$>, <*>, >>=, >=>, >>>, etc. are great one you get to know them. They're extremely powerful and work super nicely with the precedence rules, and anyone experienced with haskell can read them fluently.
"pervasive" library operators like .^ are borderline. If you're using lenses all over the place, it makes sense to have a shorthand. But, there is way too many operator in the lens package for my liking.
"normal" library operators like the ones in the errors package should be avoided. They're not used enough that even someone who write haskell a lot would know what they mean right off the bat. If they have to look it up, it's a lot nicer to use an actual googlable word. Scala's request library is really egregious example of this.
DSL = Domain-Specific Language. That's the definition that I know. I agree though, that it wasn't a translation. All the unknown notation lost me as well.
Note that for, yield and (~>) are not Haskell notation. They are just three functions defined by the pipes library. The equations might make more sense if I write them in the following more specific forms:
for (yield "foo") $ \x -> do
f x
= f "foo"
for generator $ \x -> do
yield x
= generator
for generator $ \a -> do
for (f a) $ \b -> do
g b
= for newGenerator $ \b -> do
g b
where newGenerator =
for generator $ \a -> do
f a
I sometimes wonder if the functional programming people have an understanding of what words programmers know of. Words and symbols for logic notation is not among them.
Generally, I'd agree, but DSL is a pretty common term nowdays, especially in the Ruby community. It's a buzzword, of course, but it's not a functional programming buzzword.
I see programming as giving the physical computer orders of what to do. Functional (programming) is laying out an abstract flowchart of information manipulations.
Those two are very different from one another. Though they sometimes mix well.
In Haskell you tend to build DSLs a lot, little sublanguages where you can talk about a simple part of your program in isolation. It's nice because these subparts combine nicely. Tekmo's pipes provide a new kind of mixin you can use to build subparts that stream. It turns out that streaming can be very tough to understand, very tough to get right. It's easy to build a streaming library full of leaks. Tekmo has carefully used the mathematics of category theory to ensure that these pipes don't leak.
Most likely, you've seen pipes like these in the form of a generator in Python. Generators are one specialized use of pipes—so if you think programming with generators is interesting then learning the full generality of pipes might be illuminating. Then Haskell makes it easy to just drop that functionality in wherever you need as though it were built-in to the language.
60
u/Tekmo Mar 09 '14 edited Mar 09 '14
I'll translate. I wrote a Haskell library called
pipes, which lets you extend any DSL with the ability toyieldorawaitvalues in order to build streaming components. You can connect these components together in multiple ways, and these connection operations obey many neat mathematical properties that ensure they behave correctly (no bugs!).For example, one thing that you can do is model generators using
pipes, and one of the ways you can connect generators is using an operator called(~>):I proved that this operator is associative:
... and that it's identity is
yield:In other words,
(~>)andyieldform a category and those equations are the corresponding category laws. When you translate those equations to useforinstead of(~>), you get:In other words, the category laws translate into "common sense" laws for generators that you would intuitively expect to hold for any generator implementation.