12 ms·
Functional languages interest me, but are not very approachable. I mean I looked at the examples[1] page for Idris and came away completely confused, why he hel
by orf 13y ago
Functional languages interest me, but are not very approachable. I mean I looked at the examples[1] page for Idris and came away completely confused, why he hell does this sequence of characters "data Nat = Z | S Nat" define a natural number? Or "data Maybe a = Nothing | Just a" somehow defines an option type.
It would be good to have an introduction for people not too familiar with functional languages.
1. http://www.idris-lang.org/example/ http://www.idris-lang.org/example/
- gnuvince 13y agoIt's the traditional, inductive definition of natural numbers. You give a base case (Z = Zero) and an inductive case (S Nat = Successor of Nat). So Z is a natural number, S Z is also a natural number and corresponds to 1, S (S Z) corresponds to 2, etc.
- platz 13y agoWhile not incorrect, I think the "functional language" designation is overly broad. Worst case, I'd hate for people to get turned off of functional languages because of difficulties understanding a relatively-advanced dependently-typed language such as Idris. IMHO, A language more suitable for introducing functional programming may be Clojure, F#, Scala, or just 'plain' Haskell.
- jonsterling 13y agoClojure has little relevance to functional programming: functions are the smoke, but types are the fire. F# might be a good choice for an introduction though (if you're willing to sacrifice the good parts of ML for the bad parts of .Net). Scala and Haskell both have (in decreasing order) massively more complicated type systems than Idris, so I would certainly not recommend those! Moreover, good Scala and Haskell code tends to be way more difficult to understand initially than good Idris code. YMMV. An introductory language needs to be simple enough that a learner can hold all of it in her/his head. SML and Idris fit that bill, IMO, in a way that Haskell and Scala cannot.
- platz 13y agoWe won't get anywhere without a definition, but I think most would disagree about the Clojure coment. They even assert it on the home page http://clojure.org http://clojure.org . It's probably better to think of FP as a continuum rather than black and white. While Idris may be able to eliminate some of the typing constructs in Haskell, I don't think one can say it would be easier to program in than Haskell. The chain of having to assert proofs to the compiler is an extra burden (i.e. refl). Also, saying that a Pure FP language (Idris) is easier than a non-pure language (Scala), for someone without extensive FP backround, is an interesting comment. Part of the intimidation of Haskell is it's purity, and this extends to Idris.
- jonsterling 13y ago"Practical" Haskell programming very quickly devolves into carefully constructed stacks of monad transformers. "Practical" Idris programming lives in a modality of extensible effects. These are objectively easier to get started with. (Moreover, I did also include SML in my list of languages better for beginners than Haskell and Scala incidentally. If the purity is the problem, then SML is a great place to start. Begin with proving by induction that an SML program is pure or impure—this will motivate having it internalized in the type theory.) Moreover, you don't even need to use the "proving" parts of Idris. You can use the fragment of Idris which is a fixed Haskell, and move on up to the more interesting bits when they become useful to you. For instance, you can write partial programs (and coprograms) in Idris without doing any proofs; then at the end, you can have someone help you shore it up with proofs that it is sound.
- thinkpad20 13y agoI don't know that much about Idris, but from my understanding, its type system is more advanced than Haskell's, because dependent types by definition contain more information than the (independent?) types used in Haskell (can't comment on scala). Haskell as a language with all of its various extensions and bells and whistles is surely far more complicated, having been around a great deal longer and with a massive compiler and numerous features, but from my knowledge it's incorrect to say Idris is simpler than Haskell, at least in regards to its type system.
- dragonwriter 13y ago> Why he hell does this sequence of characters "data Nat = Z | S Nat" define a natural number? Because a natural number is either zero (the one value of type Z, which has a nullary type constructor and therefore only one value) or (represented by the vertical bar "|") the successor to another natural number (represented by type S, which has a one-arg constructor whose argument is of type Nat.) Its a recursive type definition, with a base case and a recursive case. > It would be good to have an introduction for people not too familiar with functional languages. It would be; right now, you are probably be best served by one of the ones for Haskell -- Idris doesn't seem to have a lot of documentation not aimed at people not already familiar with functional programming, and really familiarity with Haskell seems to be the most applicable to Idris. The Idris tutorial [1] assumes familiarity with Haskell, but does provide brief descriptions of the relevant syntax which may be enough. [1] http://eb.host.cs.st-andrews.ac.uk/writings/idris-tutorial.pdf http://eb.host.cs.st-andrews.ac.uk/writings/idris-tutorial.p...
- captainmuon 13y agoWhile it's mathematically conventional and maybe event elegant to represent integers that way, isn't it ridiculously inefficient to actually implement it that way? I guess there is going to be something in the compiler that recognizes and special-cases this pattern, but still... Also, I really wonder why there is no language with "nice"/"conventional"/C/ALGOL/... syntax for dependent types. Right now my dream language would be something like Spec# (which is C# with contracts), but it would try to prove its contracts (within the bounds of possibility of course, wrt. the halting problem and so on).
- dragonwriter 13y ago> While it's mathematically conventional and maybe event elegant to represent integers that way, isn't it ridiculously inefficient to actually implement it that way? It would be, but the compiler recognizes the pattern and does ordinary integer arithmetic where it needs to (the pattern is relevant, however, to the use of individual natural numbers in defining other types, which is pretty important to Idris.) > Also, I really wonder why there is no language with "nice"/"conventional"/C/ALGOL/... syntax for dependent types. I don't think C/ALGOL-style syntax is all that nice when it comes to even Haskell's level of typing, much less dependent types. That said, if dependent typing takes off, no doubt we'll see languages that fuse it with C-style syntax soon after, just as we saw with OOP and basically every other thing since.
- tel 13y agoAt its simplest, `data <Name> = <Impl>` establishes a new type named <Name>. The <Impl> side describes the implementation of the type <Name> in "algebraic data type" syntax. Algebraic Data Types are types formed from "products and sums" or, in more normal usage, unions and variants. For instance, Booleans are a basic sum ADT: data Boolean = True | False and 3D points a standard union ADT: data Point = Point Double Double Double The <Impl> not only specifies the structure of the type but also its "constructors". These are automatically generated functions which can be used to build a value of a type from its constituent parts. In particular, for Boolean the constructors are True and False (each one a nullary function) and for Point the constructor is (confusingly, but conventionally) named `Point` and it takes 3 Doubles to form a Point. True : Boolean False : Boolean Point : Double -> Double -> Double -> Point Generally, we can combine these two notions of types, sums and products, as we like. Typically an <Impl> looks like a "sum of products" like data HTTPHeader = ContentType MimeType | Accept MimeType | Host String ... which generates the constructors ContentType : MimeType -> HTTPHeader Accept : MimeType -> HTTPHeader Host : String -> HTTPHeader ... So, we define the natural numbers, [0,1..], by starting at zero and counting upward. data Nat = Zero | Succ Nat which introduces a new, interesting idea that ADTs may be recursive. This means that we have two constructors Zero : Nat Succ : Nat -> Nat and, with a little play, we can see that all values of Nat must look something like the following Zero Succ Zero Succ (Succ Zero) Succ (Succ (Succ Zero)) Succ (Succ (Succ (Succ Zero))) ... and so we say that Nat represents the natural numbers because any value of that type can be converted to a number by counting the number of times Succ is used. In particular, we can write a recursive function num : Nat -> Int num Zero = 0 num (Succ n) = 1 + num n where the left side uses one final, crucially important, component of ADTs—the ability to "pattern match" on their structure. This bit is a complete mind blower the first time you see it, but it effectively follows as mere parallelism to the idea that we construct types using Constructors as functions—we "destruct" types, convert them to some other piece, by pattern matching on the Constructors as patterns. (This duality is actually really key and goes by the name of "Gentzen's Inversion Principle", not that that really matters.) The final question, about why Maybe is a definition of the option type, should look a little more clear by this point. That said, it betrays a simplification I've used thus far in that <Name> might not be a simple name, but instead a parameterized one where these parameters now occur in the ADT as well. To see if that makes a little sense, try replacing the lowercase parameter names with other concrete types like `Nat` and `Boolean`.
- captainmuon 13y agoRight, I'm a big fan of functional programming, but I never got warm with functional languages. One big reason is the syntax. I'd love to be able to specify (in pseudo C(++): typedef positive_int: int { ensure {this > 0} } typedef ambulance: vehicle { ensure {this.has_siren && this.has_bed && this.color == "red"} } and so on. (aside: The other main problem I have with functional languages is the following, I'm not sure what to call it but it bites me every time: You finally find out how to do what you want in an elegant functional way, you code it up and you're happy. Then, you want to make a small modification, but it turns out that it's impossible with the current code, and you have to rewrite everything with much less abstraction. I can't remember a great example from the top of my head, but a simple one is, you'd like to add a progress bar to a computation. It's trivial in imperative languages, but much harder in functional style.)
- discreteevent 13y agoProf. Van Roy gives a good example of this in the Edx course "Paradigms of Computer Programming" He uses the simple example of trying to introduce code to a pure functional program that will record the number of times a particular function is called. To do this you need to modify the signature of every function on the call stack. No doubt there's some other way to do this and it probably involves a monad but he was dealing with a simple pure functional language in the example. His point was that in this sense the pure system is not modular.
- platz 13y agoPure functional languages have this advantage: all flow of data is made explicit. And this disadvantage: sometimes it is painfully explicit. Of course, you could just pull a Clojure and throw everything into maps.
- sold 13y agoThat's exactly the point of monads - see http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/ba.... Such a system is still pure, btw.
- fzltrp 13y agoIf you know what enums are, think of algebraic data types as enums on steroid. You define an enum type as a set of unique values. ADT let you do the same, but let you also parameterize the enum values, and even use the enum type itself as a parameter type (a recursive definition). You can also make several ADTs mutually recursive. As other said, that's very handy to represent usual data structures like lists, trees.