Is there a way to define map using foldr in Racket similar to this (Haskell)?: map f = foldr ((:) . f) []
of course, it can be done using something like: (foldr (lambda (x ac) (cons (f x) ac)) ’() ls)
but is it possible to use composition to define the (a -> b) function, or is that impossible due to Racket’s foldr specifically taking a 2 argument combining function?
@sydney.lambda: (define (map f l) (foldr (compose f (curry cons)) null l) should work
thank samth, but sadly that gives me a contract violation with (map add1 ’(1 2 3)) ; add1: contract violation ; expected: number? ; given: ’(3)
The composition order is backwards, so it would have to be (compose (curry cons) f), but that won’t actually work either because Racket’s compose composes n-ary functions while Haskell’s (.) only composes unary functions.
It works out in Haskell because all functions are actually unary, since they’re curried. So it works out that (:) . f will apply f to a value before passing it to (:), which will then return a new function… so in the end, the result is that g . h applies h to g’s first argument and leaves the others alone.
In Racket, (compose g h) creates a new function with the same arity as h, which passes all of its result values as arguments to g.
In this case, the quirk of Haskell’s (.) operator makes it easier to write that more point-free, but it’s definitely not better in general, since it won’t do the right thing when you want to compose g with h where h has arity 2.
#lang racket
(define (uncurry f)
(lambda args
(let loop ([f f] [args args])
(if (null? args)
f
(if (procedure? f)
(loop (f (car args)) (cdr args))
f)))))
(define (map f l) (foldr (uncurry (compose (curry cons) f)) null l))
(map add1 (list 1 2 3))That works! Though the procedure? check in your definition of uncurry seems suspect to me; it seems like it ought to just fail.
yeah I didn’t think to hard about the implementation; I spent more time searching for an existing one since I thought someone had written yrruc already
Writing a proper uncurry in Racket, truly dual to curry, would be tricky, since you probably want ((uncurry (curry +)) 1 2 3) to produce 6, but that implementation of uncurry would try to evaluate (3 3), I think.
But you could make it work if you looked at procedure-arity, since curry cooperates with that now.
Thank you both! :slightly_smiling_face: Have either of you ever experimented with auto-curried Lisps? I’ve asked a few times in a few different places and got a variety of different answers, ranging from “I implemented it and it worked perfectly” to “don’t bother, it’s not worth the hassle”
I suppose that sort of thing is always going to be divisive, though
Hackett is an auto-curried Lisp, but maybe that’s cheating.
In general, making everything curried doesn’t really work with variable-arity functions, which Lisps historically use a lot.
I was just about to mention! that’s what came up a lot. That and laziness; I think because you don’t have to explicitly count the arguments, they’re just applied as-and-when until they’re all eventually passed and it’s evaluated?
yeah I have 0 faith in that code at all — it mostly just demonstrated the idea
I don’t think laziness and making everything curried are actually related
Good to know :slightly_smiling_face:
Currying is just a technique for encoding arbitrary fixed arity functions with unary functions.
λ a b c. .... just becomes λ a. λ b. λ c. ....
“Partial application” in that universe isn’t really “partial,” you just supply a couple arguments and get a function back. But of course humans still think about it as “partial application” because we think of operations like (+) as being 2-ary functions, not unary functions that return unary functions.
This is why Haskell isn’t really “auto curried,” it’s just curried. And Racket’s curry operation doesn’t really curry functions, it turns them into functions that accumulate arguments dynamically and apply the function once enough have been accumulated. But the use is similar enough that I guess the name is still useful.
A real curry in Racket would turn (lambda (a b) ....) into (lambda (a) (lambda (b) ....)), but Racket’s curry allows the result to still be applied to multiple arguments at once, since otherwise you’d have to write a lot of parentheses…
I suppose I never thought of “turning them into functions that accumulate arguments…” are being perceptibly different from currying, but I’m not as well versed on the specifics.
ah, yes, you’d have to nest parentheses.
((+ 1) 2)
bad example, but I understand.
Curried functions don’t “accumulate” arguments in the sense that they store arguments in a list and apply the function to them all at once, they’re just higher-order functions that return functions.
Of course, the function (lambda (a) (lambda (b) (f a b))) does, in some sense, “accumulate” arguments in the closure before applying f to all the accumulated arguments.
But Racket’s curry does much deeper magic than that.
The reason this is tolerable in Haskell is that it’s baked into the syntax. In Haskell, f x y z is parsed as ((f x) y) z. You could do this in a Lisp, too, so (f x y z) could be parsed as (((f x) y) z) and indeed, this is what Hackett does. But you’ve lost the ability to distinguish between the user writing ((+ 1 2) 3) and (+ 1 2 3), so you can’t really have variable-arity functions as soon as you do that.
Ah! That’s exactly what came up in one of the discussions I had around this. They spoke about changing the associativity.
I only wish I could find/remember it correctly instead of butchering what they said by half-remembering it.
just for posterity, I found it: "One thing I’ve considered is writing a lisp that associates to the left instead of right.
E.g. (a b c d) would be syntax sugar for (((a . b) . c) . d) instead of the traditional (a . (b . (c . (d .()))))
The advantage is that multiple successive partial applications become definitionally equal to application to multiple arguments."
Who wrote that? I don’t think it makes very much sense, but maybe I’m missing some context.
I think the commenter is confusing denotation and syntax there.
In Lisp, function application is represented syntactically using singly linked lists that associate right, but that doesn’t mean (f x y) applies x to y then applies f to that result.
The concrete syntax used to represent application in source code doesn’t directly correspond to what the evaluator does.
Sadly, I think I’m out of my depth here, haha. Thank you for taking the time to go over those topics for me though, I appreciate it :slightly_smiling_face:
Thanks for your generic collections library too - it’s awesome.
If it helps, I think your response to the commenter was actually spot on when you wrote this: > In regular lisp, how does it work instead? If it’s instead (f (a (b (c)))) does it mean, evaluate c (to itself), then b, a, then evaluate f on all of those? The answer is: it doesn’t work like that, but the argument the commenter was making would imply that it would, which is why it doesn’t make sense.
(Unless that wasn’t you; I guess I’m assuming OP in that thread was you, but I don’t really have any reason to believe that.)
That actually helps a lot! At least I know my intuition was right at that point.
Yup, I’m the OP.
I would be wary of the “homoiconicity” cult; it doesn’t mean nearly as much as people think it does. ;)
Haha, duly noted! I just take it to mean, the language is expressed in data structures that the language itself can easily manipulate. Really, I don’t know :wink:
the problem is that’s true of basically all languages
It’s one of those terms that people use to describe some vague collection of properties, but I’ve never met anyone who can give a useful precise definition.
Hand wavey: something quote mumble cons cough cough car
When I’ve had discussions with people, it usually boils down to one of two arguments: people either say what Racket calls quote is essential, or they say what Racket calls quote-syntax (and the associated macro machinery) is essential. If the former is true, then homoiconicity is super boring, since it’s no more useful than what other languages call “array/list/map/object literals.” If the latter is true, then it needs to also include languages like Haskell, since Haskell has Template Haskell.
But normally those same people say that Haskell isn’t homoiconic, so my conclusion is that “homoiconic” to them just means “Lisp,” and it’s a fancy word they can use to assert that Lisp is better than other languages.
@lexi.lambda I think quote adds something different — you can put quote in front of any Racket form and it “works”, which you can’t do with array literals
Okay, good point, but how is that useful?
IMO, without eval, it isn’t. And JS has eval.
I can surround any JS program with "s and it “works” in the same way.
In any case, I don’t get the sense that people are excited about homoiconicity because they’re using eval all over the place, but maybe I am misled.
The debug macro has a good example of how that’s useful
But doesn’t that assume the quote-syntax use exists?
Template Haskell can do debug, too.
no?
It’s true that most Lisps merge quote and quote-syntax into just quote, but that’s why I said “what Racket calls quote-syntax”.
AFAICT, people say quote is cool for two general reasons: its runtime uses and its compile-time uses. That’s all I meant by quote vs quote-syntax, really.
I think (define-syntax-rule (debug e) (begin (displayln 'e) e)) has a non-trivial use of quote that’s not just either quote-syntax or array literals
I see, you mean the synthesis of the two via expanding to quote.
I don’t think that’s really about quote, it’s about converting code to a string. In Template Haskell, I could write debug expr = [e\|putStrLn $(pure . lift $ show expr) >> $(pure expr)\|].
@lexi.lambda then you have to add a quote at the use site, and note that there’s not a universal quote for haskell syntax
I don’t see how that’s relevant, personally, there just as well could be, and it would still be the quote-syntax use, not quote.
My point is that you can write debug with quote-syntax but without quote: sweet.js can do it, procedural Rust macros can do it, TH can do it, etc. So I don’t see what’s important about quote.
If you’re arguing that TH isn’t a good macro system, sure, I’d be all for that. But we’re talking about homoiconicity. :)