5 ms·

Some questions. Background: I'm coming to the whole world of functional programming via Ruby (via C). Doesn't Clojure have purely functional (immutable) data s

Some questions. Background: I'm coming to the whole world of functional programming via Ruby (via C). Doesn't Clojure have purely functional (immutable) data structures? Whenever this area is talked about I always hear Clojure mentioned. Do other functional languages have libraries (standard or otherwise) of these? Are these data structures implemented in Clojure itself? I kind of see Ruby like a hybrid functional language. Could Ruby be used to implement the data structures in this book, or would that be like a square peg in a round hole? Didn't Ruby recently get official lazy evaluation? Hum, so many questions, so little Google :(

DanWaterworth 14y ago
> I kind of see Ruby like a hybrid functional language. Functions aren't even first class in Ruby (though it does have closures). I certainly wouldn't describe it as a hybrid functional language.
- riffraff 14y ago
  I'd refrain from saying "functions aren't first class in ruby", unless you qualify the assertion. E.g. you could mean "you can't call functions by just adding () at the end", or "the block syntax only allows passing one function", but these are both just syntax differences. On the other hand, you can create standalone functions, pass them around, introspect them, invoke them, call methods on them and compose them, which is more or less what you can do with integers in python (we can agree integers are first class objects in python, I think) So there may be reason for saying they are "not first class", but you should expand on it.
  - DanWaterworth 14y ago
    You're right, I should have backed up that assertion. The reason I say that functions aren't first class is that if you create a function: def factorial(n) if n > 0 n * factorial(n - 1) else 1 end end You can't pass it into another function without creating an object for it. ie, using Kernel.method(:factorial). It's the same with blocks, they aren't first class, in order to construct values, you have to construct objects that holds them.
    - stouset 13y ago
      So? I can easily write >> Y = ->(&x) { ->(f) { f[f] }[ ->(g) { x[ ->(*n) { g[g][*n] } ] } ] } >> fac = Y.call {|this| -> (n) { n > 0 ? n * this[n - 1] : 1 } } >> fac[5] => 120 You can argue that Ruby doesn't lend itself towards higher-order functional programming, but I asserting that Ruby isn't a function language isn't a tenable position.
      - DanWaterworth 13y ago
        Do you deny that factorial, as I implemented it, is a function? Do you deny that I can't pass factorial into another function without creating an object to hold it? It doesn't matter what else is true. These facts alone mean that ruby's function's aren't first class.
pavelludiq 14y ago
Common Lisp is in the same category as a FP-ish language but still mostly used in a mutable OO fashion. We have a library called FSET written in CL to add persistent data structures and convenient syntax for them to the language. I don't know how powerful ruby meta-programming is, but I imagine it isn't as easy to do(like add a syntax for persistent maps that is as convenient as the built in one). Not to mention that ruby has a reputation for much worse performance than CL, so you'll likely have to use FFI and write most of it in C. As for clojure, I think they are all implemented in java, but I haven't been following clojure development in two years, so maybe with protocols they moved them(or could) to clojure? I don't know.
noelwelsh 14y ago
Yes, Clojure does have many purely functional data structures built in to its core. I don't know the precise implementations, or if they're written in Clojure or Java, but I believe they're based on the work of Phil Bagwell. Every functional language implementation I know of has many of these data structures available as a library somewhere. You certainly could implement these data structures in Ruby, though it's likely they wouldn't mesh as well as in a more functional language. This Stackexchange answer has links to many papers if you're interested in more: http://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki http://cstheory.stackexchange.com/questions/1539/whats-new-i...
- mtrimpe 14y ago
  Clojure was also the first mainstream (non-PF) language to implement Okasaki's as first class data structures. I know Scala quickly followed suit, since I remember Odersky bragging in a meetup that he went out of his way to find the scientists that improved on Okasaki's work and based Scala's data structures on their work instead.
sfrank 14y ago
Sure you can do however, since Ruby allows destructive updates, why not use one of the established/traditional imperative data structures and then apply techniques to make them "persistent" (i.e. immutable in the functional programming sense as is also used by Okasaki and of course not using the trivial technique of copying the whole thing). Such techniques are e.g. presented in CLRS if I remember correctly. It is not that Okasaki was the first one to implement any functional data structure. People have been doing this before and also in purely functional languages such as Haskell, ML, or Opal). He was the first to give a very nice overview, showed some new designs and even more important, showed a way for time complexity analysis (in a lazy evaluation context). And it is this last part of the thesis that many people overlook: the importance of lazy evaluation (and thus the implied fundamental optimizations/evaluations performed by the compiler/runtime) for most of the presented data structures (i.e. everything with an amortized time complexity). Simply implementing Queues as presented in the thesis and not having a lazy language will lead to a very different time complexity than is proven there, because lazy semantics is vital for the given complexity analysis. This is also the reason, why e.g. Clojure (or Opal from the early 90s, [1]) use other data structures to ensure functional (i.e. persistent) semantics in an eager/strict evaluation model. [1] 1994, http://projects.uebb.tu-berlin.de/opal/trac/raw-attachment/wiki/Papers/DesignImplOpal.ps.gz http://projects.uebb.tu-berlin.de/opal/trac/raw-attachment/w...
WildUtah 14y ago
Rich Hickey says during talks that Clojure's persistent data structures are based on this book and inspired by the Haskell implementation. The book is in Hickey's recommended reading list. Language designers should pursue the books in that list; it's a good one. http://www.amazon.com/Clojure-Bookshelf/lm/R3LG3ZBZS4GCTH http://www.amazon.com/Clojure-Bookshelf/lm/R3LG3ZBZS4GCTH The main Clojure ('JClojure') implementation has these written in Java but Clojurescript has a pure Clojure implementation and there are Clojure-in-Clojure projects that do the same. The Java versions are still slightly faster on the JVM, unless things have changed. Clojure does not require you to program in pure functional style like Haskell. You can even write Clojure code with no immutable data structures and always use the Java paradigm data structures instead, though I do not recommend it. The support for mixing both paradigms and also transactional memory are part of the defining flexibility of Clojure. It's not a bondage and discipline affair; Clojure has a strong aesthetic but you can code however you want when you need to. I think Scala has similar data structures, also.

DanWaterworth 14y ago

> I kind of see Ruby like a hybrid functional language. Functions aren't even first class in Ruby (though it does have closures). I certainly wouldn't describe it as a hybrid functional language.

riffraff 14y ago
I'd refrain from saying "functions aren't first class in ruby", unless you qualify the assertion. E.g. you could mean "you can't call functions by just adding () at the end", or "the block syntax only allows passing one function", but these are both just syntax differences. On the other hand, you can create standalone functions, pass them around, introspect them, invoke them, call methods on them and compose them, which is more or less what you can do with integers in python (we can agree integers are first class objects in python, I think) So there may be reason for saying they are "not first class", but you should expand on it.
- DanWaterworth 14y ago
  You're right, I should have backed up that assertion. The reason I say that functions aren't first class is that if you create a function: def factorial(n) if n > 0 n * factorial(n - 1) else 1 end end You can't pass it into another function without creating an object for it. ie, using Kernel.method(:factorial). It's the same with blocks, they aren't first class, in order to construct values, you have to construct objects that holds them.
  - stouset 13y ago
    So? I can easily write >> Y = ->(&x) { ->(f) { f[f] }[ ->(g) { x[ ->(*n) { g[g][*n] } ] } ] } >> fac = Y.call {|this| -> (n) { n > 0 ? n * this[n - 1] : 1 } } >> fac[5] => 120 You can argue that Ruby doesn't lend itself towards higher-order functional programming, but I asserting that Ruby isn't a function language isn't a tenable position.
    - DanWaterworth 13y ago
      Do you deny that factorial, as I implemented it, is a function? Do you deny that I can't pass factorial into another function without creating an object to hold it? It doesn't matter what else is true. These facts alone mean that ruby's function's aren't first class.

pavelludiq 14y ago

Common Lisp is in the same category as a FP-ish language but still mostly used in a mutable OO fashion. We have a library called FSET written in CL to add persistent data structures and convenient syntax for them to the language. I don't know how powerful ruby meta-programming is, but I imagine it isn't as easy to do(like add a syntax for persistent maps that is as convenient as the built in one). Not to mention that ruby has a reputation for much worse performance than CL, so you'll likely have to use FFI and write most of it in C. As for clojure, I think they are all implemented in java, but I haven't been following clojure development in two years, so maybe with protocols they moved them(or could) to clojure? I don't know.

noelwelsh 14y ago

Yes, Clojure does have many purely functional data structures built in to its core. I don't know the precise implementations, or if they're written in Clojure or Java, but I believe they're based on the work of Phil Bagwell. Every functional language implementation I know of has many of these data structures available as a library somewhere. You certainly could implement these data structures in Ruby, though it's likely they wouldn't mesh as well as in a more functional language. This Stackexchange answer has links to many papers if you're interested in more: http://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki http://cstheory.stackexchange.com/questions/1539/whats-new-i...

mtrimpe 14y ago
Clojure was also the first mainstream (non-PF) language to implement Okasaki's as first class data structures. I know Scala quickly followed suit, since I remember Odersky bragging in a meetup that he went out of his way to find the scientists that improved on Okasaki's work and based Scala's data structures on their work instead.

sfrank 14y ago

Sure you can do however, since Ruby allows destructive updates, why not use one of the established/traditional imperative data structures and then apply techniques to make them "persistent" (i.e. immutable in the functional programming sense as is also used by Okasaki and of course not using the trivial technique of copying the whole thing). Such techniques are e.g. presented in CLRS if I remember correctly. It is not that Okasaki was the first one to implement any functional data structure. People have been doing this before and also in purely functional languages such as Haskell, ML, or Opal). He was the first to give a very nice overview, showed some new designs and even more important, showed a way for time complexity analysis (in a lazy evaluation context). And it is this last part of the thesis that many people overlook: the importance of lazy evaluation (and thus the implied fundamental optimizations/evaluations performed by the compiler/runtime) for most of the presented data structures (i.e. everything with an amortized time complexity). Simply implementing Queues as presented in the thesis and not having a lazy language will lead to a very different time complexity than is proven there, because lazy semantics is vital for the given complexity analysis. This is also the reason, why e.g. Clojure (or Opal from the early 90s, [1]) use other data structures to ensure functional (i.e. persistent) semantics in an eager/strict evaluation model. [1] 1994, http://projects.uebb.tu-berlin.de/opal/trac/raw-attachment/wiki/Papers/DesignImplOpal.ps.gz http://projects.uebb.tu-berlin.de/opal/trac/raw-attachment/w...

WildUtah 14y ago

Rich Hickey says during talks that Clojure's persistent data structures are based on this book and inspired by the Haskell implementation. The book is in Hickey's recommended reading list. Language designers should pursue the books in that list; it's a good one. http://www.amazon.com/Clojure-Bookshelf/lm/R3LG3ZBZS4GCTH http://www.amazon.com/Clojure-Bookshelf/lm/R3LG3ZBZS4GCTH The main Clojure ('JClojure') implementation has these written in Java but Clojurescript has a pure Clojure implementation and there are Clojure-in-Clojure projects that do the same. The Java versions are still slightly faster on the JVM, unless things have changed. Clojure does not require you to program in pure functional style like Haskell. You can even write Clojure code with no immutable data structures and always use the Java paradigm data structures instead, though I do not recommend it. The support for mixing both paradigms and also transactional memory are part of the defining flexibility of Clojure. It's not a bondage and discipline affair; Clojure has a strong aesthetic but you can code however you want when you need to. I think Scala has similar data structures, also.