Actually, these examples are similar to the first example in my post (under the first "pathological case" heading) and don't quite exhibit the worst case behavior since the type can be represented in linear space as a dag.
Thanks for pointing that out! I hadn't made the connection and now I've got another reason to figure out how fold works (have yet to wade through all of http://mlton.org/Fold)
It's unlikely to occur as the type is exponential in size and thus quite unwieldy to do anything with! I haven't worked with generated ML or Haskell code, but I still think it's unlikely to be an issue in "real" code.
That's very interesting! This seems to me like it might be a different kind of edge case though, since the type of x is still t -> t, even if it takes a long time for the type checker to arrive at this. From the little I got out of Mairson's paper, it seems that the proof he uses depends on the exponential size of the type itself, but I could be mistaken... either way I wonder how they're related?
Rent the Runway - New York, NY (VISA candidates welcome!)
Rent the Runway is building the first online rental platform for retail goods. We're a disruptive e-commerce business that believes democratizing luxury products in the US is just the first step of a broader vision to drive aspirational experiences for tens of millions of users across the globe. We're more than "Netflix for dresses"—we're Cinderella Experience as a Service. Find out more about the challenging product-oriented problems we face across the boundaries of e-commerce, mobile, analytics and shipping/fulfillment here: http://blog.tech.renttherunway.com/
We are hiring front-end, back-end, DevOps, and mobile (iOS) engineers. Our stack:
* Service-oriented architecture with Java 7 (soon to be 8!) and DropWizard: Modern Java is a thing and we've got the proof!
* Ruby and Sinatra for lightweight, scalable web applications.
* JavaScript and Backbone for a front end that's becoming faster and more awesome to work on every day.
Rent the Runway is hiring all sorts of engineers (Java, Data, iOS, full stack) in the NYC area.
Rent the Runway is building the first online rental platform for retail goods. We are a disruptive e-commerce business that believes that democratizing luxury products in the US is just the first step of a broader vision of helping drive better aspirational experiences for tens of millions of users across the globe.
Our engineering team works on challenging product-oriented problems across the boundaries of e-commerce, mobile, analytics and shipping/fulfillment, and the backbone of our business is served by our custom logistics management system which is core to our capacity to deliver the right product to the right user at the right time. We utilize data, engineering and algorithms to create a personalized website and an adaptive supply chain to fulfill our commitment to an amazing customer experience.
Engineers at Rent the Runway focus on solving business problems first, and receive the satisfaction that they have true impact on the success of the company. Many of our engineers are entrepreneurs themselves, and we strongly encourage a collaborative, product-driven culture across our organization. We have a very diverse team and welcome those with supernerd CS degrees as well as those with non-traditional backgrounds.
Short answer: I don't think LYAH would be entirely sufficient background, and I think familiarity with imperative equivalents is a prerequisite, but along with some other background.
Long version: I stumbled a bit when trying to read this book, because I'm not super comfortable with the formal techniques for analyzing algorithms. I'm not talking about the kind of fluffy-tech-company-interview-"knows what big Oh is and can estimate it roughly on a whiteboard" ability but actually something much more concrete and formal, the kind taught in an undergrad algorithms class or in CLRS. I've taken those classes, I have CLRS on my shelf and have read some of it, but it's been a long time and it's not at my fingertips. There are exercises in the book ("prove that this data structure has this amortized performance", "prove that it does if you change this one thing", etc...) that challenged me quite a bit, and I ended up putting it down after a while thinking I would revisit it after refreshing my fundamentals.
The ML code is easy enough to follow if you know Haskell, but since the point is often to understand the subtlety of the performance characteristics of the data structures and algorithms, just reading and playing with the code wasn't enough for me. After all you can trivially implement functional data structures naively just by copying everything on every operation.
Frankly, Rich Hickey's videos on Clojure's data structures have done a lot more for me in terms of understanding how functional data structures work, even though they are much less formal in presentation. To be clear: I think Okasaki's book is probably a very good book and an important work, but am not so sure it is crucial for the working functional programmer to internalize all the mathematical details.
Anyway, YMMV. Check out his thesis and see what you think before buying it.
A researcher in programming languages once told me that when she encounters the "HTML isn't a programming language" meme she always thinks: Agda and Coq aren't Turing complete, are they also not programming languages?
The point being, I think, that drawing this bright line at Turing completeness doesn't hold up when you give it any thought, and so it's not very useful. Aside from that, you've utterly missed the point of the OP.
I have no idea what you're working on, but I spent a few weeks this summer writing parsers and trying to figure out how to tackle the ugliness that seems to be inherent in hand-written recursive descent parsers. While I learned a lot, I am not an expert by a long shot. However I did find an interesting technique that is not well covered elsewhere.
I came across this* article, which uses JavaScript as the implementation language, and found it very interesting, in large part because this approach (Top down operator precedence) sort of pulls the precedence hierarchy out of the call graph of a recursive descent parser and into a table, but also because it's an approach that OOP (and JavaScript in particular) is well suited to. I've used it (in combination with traditional recursive descent) in a functional setting (Standard ML) as well, and would use it again, especially for parsing infix expressions (arithmetic expressions, type annotation expressions).
This is a bit of a tangent, but I thought you might be interested given the intersection of parsing and JavaScript. I've been meaning to write this up in a short blog post...
The purpose of a question like this, and of the classic FizzBuzz question, is to be a lightweight test of whether a candidate can actually write code or not. That's all. It provides a negative signal if they fall completely to get anywhere close, and nothing more.
There are alternatives, you could ask them to explain a piece of code they wrote on their own before the interview, any piece of code would do. I suppose that could be gamed which is why most companies opt for FizzBuzz.
Personally, once I started thinking about these kinds of questions like this, I had less issue with them. Interviewing people who failed to write FizzBuzz opened my eyes too.
It's not about macros, it's about homoiconicity. I encourage you to read chapters 4 and 5 and think about how sweet.js would help you port those chapters to JS.
As others have pointed out, chapters 4 and 5 are as wonderful and rich as they are because Scheme is homoiconic which makes writing Scheme interpreters and compilers in Scheme very easy -- no need for hairy lexing and parsing steps. Since (IMHO) these chapters are the best introduction to the study of programming languages and their implementation, it would be a real shame to discard them simply because JavaScript is more widely known and used than Scheme.
It's true that the ideas in the book transcend programming languages, and that the first 3 chapters could probably could be covered in JavaScript with little modification, if a little clumsily. But rewriting the 4th and 5th to include sections on parsing JavaScript would be quite challenging, and furthermore JavaScript does not have as simple semantics as Scheme, so there would be a loss of a great deal of elegance and beauty. The metacircular Scheme interpreter can run itself, which would be harder to do in JavaScript since its core is more rich and Scheme's core: objects, methods and so on complicate it quite a bit.
C-_ is undo in Emacs. That's hold Control, and press "underscore". On my keyboard (most keyboards?) this requires holding Shift and pressing the "minus" key. Hopefully that's clear.
> When did it become something we have to love and wrap up so much of our self-image into?
When we started spending 50, 60 hours a week at work. Even at 40 hours a week, it's exhausting to try to find any real time to devote to hobbies and "extracurricular" learning outside of work. If you feel like you're stagnating, feeling like you're wasting those 40 hours of life every week, why stay, just because "work is a financial transaction" ?
IANAL but I don't think you need to worry about this too much as an application or open source developer USING Clojure the language and Clojure's standard libs. This question and its answers on Stack Overflow points to an interpretation that makes sense intuitively to me, but again, not a lawyer, pretty ignorant of this stuff, etc...
It would be nice if someone from the Clojure team would add a FAQ page or something about the license to clojure.org as it pertains to users of the language... Since this seems to come up a lot.
As others have pointed out, apparently the police can seize your property under certain circumstances. This was discussed recently when the article mentioned in this blog post was submitted here, well worth the read IMHO https://news.ycombinator.com/item?id=6161465