Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A philosophical difference between Haskell and Lisp (2015)

chrisdone.com

Post reply on HN
Print view View original

171–180 of 181 posts

Re: A philosophical difference between Haskell and Lisp (2015)

#171

Post by nybble41 »

dllthomas wrote: post #86

Uh guys? [1]> (remove-if-not #'evenp `(1 2 3 4 5 6 7 8 9 10) :count 3 :start 1) (1 2 4 6 8 9 10) As pointed out by owl57, the Haskell translation is incorrect and the correct implementation isn't quite so trivial. I don't see a way to pull the :count argument out into a separate function. We certainly can for skip, though, and I might. Prelude> skipThen 1 (removeIfNot even 3) [2,3,4,5,6,7,8,9] [2,4,6,8,9] as implemen…

You could decompose removeIfNot a bit further by representing the intermediate stages as pairs of lists (result + unprocessed input):

    import Data.Bifunctor (bimap, first)

    type Split a = ([a], [a])
    
    unsplit :: Split a -> [a]
    unsplit = uncurry (++)

    splitStart :: [a] -> Split a
    splitStart xs = ([], xs)

    skip :: Int -> Split a -> Split a
    skip n (xs, ys) = first (xs ++) (splitAt n ys)

    iterateN :: Int -> (a -> a) -> a -> a
    iterateN n f = (!! n) . iterate f

    removeOneIfNot :: (a -> Bool) -> Split a -> Split a
    removeOneIfNot p (xs, ys) = bimap (xs ++) (drop 1) (span p ys)
    
    GHCI> unsplit . iterateN 3 (removeOneIfNot even) . skip 5 . splitStart $ [1..15]
    [1,2,3,4,5,6,8,10,12,13,14,15]

Re: A philosophical difference between Haskell and Lisp (2015)

#172

Post by eru »

wrs wrote: post #98
dan-robertson wrote: post #84

Earlier quoted context omitted.

Strictly speaking, Common Lisp does not have series because they were not included in ANSI Common Lisp. Therefore even though you could use the macros provided with a separate streams package, you’d need to make sure that all your code used that package (rather than the CL definitions of let and lambda and so on) and properly declared stream functions. This ends up making code using streams not super composable which…

My impression was some of those expressions were added to the compiler specifically to make stream fusion work well enough to use. Even if so, it’s a good point that laziness makes streams more “natural” in Haskell so that was just a performance improvement, not a semantic change. Certainly laziness is a big “philosophical difference” between the two!

Yes. And laziness works because Haskell is pure-by-default.

Yes. Though if we were starting from scratch today, perhaps we would see a total language, ie one where all functions terminate.

That would allow the compiler much more freedom in how to order evaluation.

Re: A philosophical difference between Haskell and Lisp (2015)

#173

Post by eru »

ajarmst wrote: post #134
eru wrote: post #125

Earlier quoted context omitted.

> It’s pretty common to see form in lisp that ends in a dozen close-parentheses as we see chains of forms being passed as arguments to other forms. That's just a chain of function applications. Function composition puts the emphasis on the fact that functions are values in their own right and can be manipulated (eg with a composition operator) as objects without regard to any values they might act on. If you want to…

I’m not convinced that chain application and composition are meaningly distinct in anything but a syntactic sense if the language in question offers first-class functions and deterministic evaluation (eg no side effects). In mathematics, composition ($f \circ g$) is invariably described in terms of chaining f(g())—in fact, the composition operator is usually defined as alias for chaining. Yes, there are subtleties I’…

Mostly agreed.

John Backus seemed to think it was a big deal. See eg 'Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs ' (http://www.ict.nsc.ru/xmlui/bitstream/handle/ICT/1256/1977-b...)

On the one hand, I do agree that in a language like Haskell it's almost entirely a syntax level distinction.

On the other hand, syntax level conveniences and inconveniences can have a big impact on how people use a language. (Eg in Haskell if-then-else is more hassle to type out than pattern matching. A slight nudge by the language design to make users prefer the latter.)

Once you have acquired the ability to see functions as objects in their own right, many more techniques become available. Think of eg parser combinators.

Technically you don't need the syntactic convenience to use parser combinators. But I am not sure they are worth the hassle without those conveniences. Eg Python has enough functional machinery to support parser combinators, but its options for defining functions (def and lambda) are just so cumbersome.

Re: A philosophical difference between Haskell and Lisp (2015)

#174

Post by eru »

ajarmst wrote: post #136
eru wrote: post #125

Earlier quoted context omitted.

> It’s pretty common to see form in lisp that ends in a dozen close-parentheses as we see chains of forms being passed as arguments to other forms. That's just a chain of function applications. Function composition puts the emphasis on the fact that functions are values in their own right and can be manipulated (eg with a composition operator) as objects without regard to any values they might act on. If you want to…

And thanks for the link to the loop monad. I didn’t know it or forgot. I don’t know whether to be delighted or appalled.

Glad to be of service.

(Slight pedantry: I wouldn't call it the 'loop monad' in the same way as 'list monad' or 'IO monad'. The monad loop library provides looping combinators you can use with many monads and some you can use with all monads.)

Re: A philosophical difference between Haskell and Lisp (2015)

#175

Post by eru »

johnday wrote: post #146
eru wrote: post #116

Earlier quoted context omitted.

If you don't like flip, you could also do xs :: [Int] xs = 5 & (`take` [1, 2, 3]) & filter (/= 1) & head & (`take` [1, 2, 3]) But I'm not sure that's a better style than flip. I really like `on` from Data.Function, too.

For maximum readability I'd be tempted to write the lambdas explicitly. xs = 5 & (\n -> take n [1, 2, 3]) & filter (/= 1) & head & (\n -> take n [1, 2, 3])

That might be a wise choice.

It depends on what you are used to and your tolerance thresholds.

In a code base I worked on professionally, I came across the following idiom

    f a b `flip` d
which at first used to confuse me to no end. Later I figured out that you are supposed to read it as:

    f a b  d
and thus

    \c -> f a b c d
In the same vein that Scala uses an underscore in somewhat implicit anonymous function syntax.

I still wasn't really happy with that usage, but at least I see why someone thought it would make sense.

(Mostly I wasn't so happy because it only works for the penultimate argument. If the syntax had worked out so that

    f a `flip` c d
would mean

    \b -> f a b c d
I would have been more amenable to the idiom. But you need the ugly

   f a `flip` c `flip` d
for that case. And that's clearly worse than the lambda syntax.

Re: A philosophical difference between Haskell and Lisp (2015)

#176

Post by eru »

garmaine wrote: post #164
eru wrote: post #111

Earlier quoted context omitted.

Nothing wrong with applied math. It's still math.

From the grandparent post: > I followed a (pure) mathematics education...

Oh, OK, that's what you meant. Makes more sense.

I'm not so quick in judging people by how applied they are.

We mathematicians always try to come up with new pure fields, but then some other people always come and find some applications. Just see how cryptography and computer science sullied our beloved number theory!

(I mostly focused on the computer-science-y parts of math in my studies. Thinks like linear optimization and combinatorics. Not sure whether to count that as applied or pure. I guess I might get a purity pass, because we only ever proved our algorithms correct but seldom implemented them.)

Re: A philosophical difference between Haskell and Lisp (2015)

#177

Post by dllthomas »

nybble41 wrote: post #171
dllthomas wrote: post #86

Uh guys? [1]> (remove-if-not #'evenp `(1 2 3 4 5 6 7 8 9 10) :count 3 :start 1) (1 2 4 6 8 9 10) As pointed out by owl57, the Haskell translation is incorrect and the correct implementation isn't quite so trivial. I don't see a way to pull the :count argument out into a separate function. We certainly can for skip, though, and I might. Prelude> skipThen 1 (removeIfNot even 3) [2,3,4,5,6,7,8,9] [2,4,6,8,9] as implemen…

You could decompose removeIfNot a bit further by representing the intermediate stages as pairs of lists (result + unprocessed input): import Data.Bifunctor (bimap, first) type Split a = ([a], [a]) unsplit :: Split a -> [a] unsplit = uncurry (++) splitStart :: [a] -> Split a splitStart xs = ([], xs) skip :: Int -> Split a -> Split a skip n (xs, ys) = first (xs ++) (splitAt n ys) iterateN :: Int -> (a -> a) -> a -> a i…

Very nice! I had a bit of trouble convincing myself that it has the laziness I'd want out of it, but by experimentation it seems to.

Still, definitely a more complicated decomposition than that described in the article (but maybe a more interesting article!)

Re: A philosophical difference between Haskell and Lisp (2015)

#178

Post by johnday »

eru wrote: post #175
johnday wrote: post #146

Earlier quoted context omitted.

For maximum readability I'd be tempted to write the lambdas explicitly. xs = 5 & (\n -> take n [1, 2, 3]) & filter (/= 1) & head & (\n -> take n [1, 2, 3])

That might be a wise choice. It depends on what you are used to and your tolerance thresholds. In a code base I worked on professionally, I came across the following idiom f a b `flip` d which at first used to confuse me to no end. Later I figured out that you are supposed to read it as: f a b d and thus \c -> f a b c d In the same vein that Scala uses an underscore in somewhat implicit anonymous function syntax. I s…

Oh good lord, that's horrible!

Re: A philosophical difference between Haskell and Lisp (2015)

#179

Post by nybble41 »

dllthomas wrote: post #177
nybble41 wrote: post #171

Earlier quoted context omitted.

You could decompose removeIfNot a bit further by representing the intermediate stages as pairs of lists (result + unprocessed input): import Data.Bifunctor (bimap, first) type Split a = ([a], [a]) unsplit :: Split a -> [a] unsplit = uncurry (++) splitStart :: [a] -> Split a splitStart xs = ([], xs) skip :: Int -> Split a -> Split a skip n (xs, ys) = first (xs ++) (splitAt n ys) iterateN :: Int -> (a -> a) -> a -> a i…

Very nice! I had a bit of trouble convincing myself that it has the laziness I'd want out of it, but by experimentation it seems to. Still, definitely a more complicated decomposition than that described in the article (but maybe a more interesting article!)

With one more combinator we can decompose this slightly further:

    stepSplit :: ([a] -> Split a) -> Split a -> Split a
    stepSplit f = uncurry first . bimap (++) f
    
    skip n = stepSplit (splitAt n)
    
    removeOneIfNot p = stepSplit (second (drop 1) . span p)
Or in perhaps-more-familiar monadic terms:

    import Control.Monad (replicateM_)
    import Control.Monad.Trans (lift)
    import Control.Monad.Trans.State (StateT, evalStateT, state, get)
    import Control.Monad.Trans.Writer (WriterT, execWriterT, tell)
    import Data.Bifunctor (second)
    import Data.Functor.Identity (Identity, runIdentity)

    type SplitterT b m = WriterT [b] (StateT [b] m)
    type Splitter b = SplitterT b Identity

    splitter :: Monad m => ([b] -> ([b], [b])) -> SplitterT b m ()
    splitter f = lift (state f) >>= tell

    execSplitterT :: Monad m => SplitterT b m a -> [b] -> m [b]
    execSplitterT m = evalStateT (execWriterT (m >> lift get >>= tell))

    execSplitter :: Splitter b a -> [b] -> [b]
    execSplitter m = runIdentity . execSplitterT m

    skip :: Monad m => Int -> SplitterT b m ()
    skip n = splitter (splitAt n)

    removeOneIfNot :: Monad m => (b -> Bool) -> SplitterT b m ()
    removeOneIfNot p = splitter (second (drop 1) . span p)

    GHCI> execSplitter (skip 5 >> replicateM_ 3 (removeOneIfNot even)) [1..15]
    [1,2,3,4,5,6,8,10,12,13,14,15]
It's hard to say which version is clearer. It probably depends on what you're used to. The code is essentially the same under the Writer/State abstraction, with `execSplitter` replacing both `unsplit` and `splitStart` and monadic bind in place of function composition. The `Splitter b ()` type is isomorphic to the `[b] -> ([b], [b])` used for the argument to `stepSplit` in the first version.

Re: A philosophical difference between Haskell and Lisp (2015)

#180

Post by kazinator »

dllthomas wrote: post #86

Uh guys? [1]> (remove-if-not #'evenp `(1 2 3 4 5 6 7 8 9 10) :count 3 :start 1) (1 2 4 6 8 9 10) As pointed out by owl57, the Haskell translation is incorrect and the correct implementation isn't quite so trivial. I don't see a way to pull the :count argument out into a separate function. We certainly can for skip, though, and I might. Prelude> skipThen 1 (removeIfNot even 3) [2,3,4,5,6,7,8,9] [2,4,6,8,9] as implemen…

TXR Lisp with unpublished reject function (complementing select):

  (1> (let ((r (range 1 10)))
        (reject r (take 3 (drop 1 [where oddp r]))))
  (1 2 4 6 8 9 10)
This is not correct because "drop 1" means "drop the first index where r was found odd" not "drop the first index if it happens to be zero".

Fix:

  2> (let ((r (range 1 10)))
       (reject r (take 3 [drop-while zerop [where oddp r]])))
  (1 2 4 6 8 9 10)
"Let R be a sequence of integers, indexed from 0. Determine the indices where R is odd, as a sequence of indices in ascending order. Remove the zero index, if it is present. Then take the first three of the remaining indices. Remove the elements with those indices from R."

This seems verbose, but watch it do something Common Lisp's remove-if will choke on:

  2> (take 50 (let ((r (range 1 1000000000000)))
        (reject r (take 3 [drop-while zerop [where oddp r]]))))
  (1 2 4 6 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
   48 49 50 51 52 53)
range generates a lazy list. where generates the indices lazily. drop-while and take are also lazy, and I just coded reject so that, after the indices have been exhausted, if the remainder of the list is lazy, then it just tacks that lazy suffix into the output. I.e. it's not fully lazy, but in this case it works because the list of indices was trimmed to a finite length.

I think in release 242, I will might include reject, as a fully lazy version supporting a lazy, infinite list of indices as well as sequence; and will fix select to also be fully lazy.

Post reply on HN