lisp change machine

dynamic programming mixed with HOFs. originally an exam question. brain on fire for an undergrad fuckwit like myself

(define (change amt coins)
(cond
((= amt 0) '(()))
((or (<= amt 0) (null? coins)) '())
(else
(fold-right (lambda (a b) (append a b))
'()
(map
(lambda (n)
(map
(lambda (u)
(append (list n) u))
(change (- amt n)
(filter (lambda (k) (>= k n)) coins))))
coins)))))

;; -----------------------------------------------------------------------

(define (display-nl u)
(display u)
(newline))

(define display-elements
(lambda (u)
(map display-nl u)))

(define (demo r k)
(display-nl '-----------------------------)
(display r) (display ';;) (display k) (newline)
(display-nl '=============================)
(display-elements (change r k))
(display-nl '-----------------------------)
(newline))

;; -----------------------------------------------------------------------

(newline)

(demo 5 '(1 2 5))
(demo 13 '(1 3 5 7))
$ ./lisp <change.lisp

Loaded `prefix.txt'

-----------------------------
5;;(1 2 5)
=============================
(1 1 1 1 1)
(1 1 1 2)
(1 2 2)
(5)
-----------------------------

-----------------------------
13;;(1 3 5 7)
=============================
(1 1 1 1 1 1 1 1 1 1 1 1 1)
(1 1 1 1 1 1 1 1 1 1 3)
(1 1 1 1 1 1 1 1 5)
(1 1 1 1 1 1 1 3 3)
(1 1 1 1 1 1 7)
(1 1 1 1 1 3 5)
(1 1 1 1 3 3 3)
(1 1 1 3 7)
(1 1 1 5 5)
(1 1 3 3 5)
(1 3 3 3 3)
(1 5 7)
(3 3 7)
(3 5 5)
-----------------------------

ocaml version

let rec change amt coins =
if amt = 0 then [[]]
else if amt <= 0 || coins = [] then []
else
List.fold_right (fun a b -> a @ b) (
List.map
(fun n ->
(List.map
(fun u ->
n :: u)
(change (amt - n)
(List.filter (fun k -> k >= n) coins))))
coins) []

define

Why not def?

>>3

It is written in Scheme, and I learnt Scheme from SICP which as best as I recall gives its examples using define. But I am willing to learn new syntaxes if they are superior.

>>4
(define-syntax def
(syntax-rules ()
((def a ...)
(define a ...))))

(define-syntax lam
(syntax-rules ()
((lam a ...)
(lambda a ...)))))

That's not Lisp, that's Scheme.

>>6

Sorry about that, SICP background showing again. in the lectures they use Scheme throughout but refer to it verbally as "Lisp". I will be careful to be more pedantic in future

>>6
fuck off back to #lisp on freenode

>>7
ignore that cunt, scheme is a lisp. common lisp does not own the word lisp.

awful indentation

>>8
ignore that cunt, java is a smalltalk. smalltalk-80 does not own the word smalltalk.

>>10

Well either way, I will agree that it is probably less ambiguous to say Scheme. There are many languages in the Lisp family..

>>6
McCarthy dubbed Steele "boss" of lisp. Steele calls Scheme Lisp. Give it up you frauds.

Javascript is more of a Lisp than Common Lisp, anyway.

>>10

this contrived analogy proved you wrong

no

>>13
He didn't say that.

>>12

this contrived analogy proved you wrong

no

>>15
He didn't say that either. Why are you doing this? Your mom must have dropped you from a considerable height.

>>12

McCarthy dubbed Steele "boss" of lisp

Interesting tidbit, I looked it up, http://www.infoq.com/interviews/Steele-Interviews-John-McCarthy

If Lisp has any boss, it's you [Guy Steele]! You wrote the reference manual.

It's a shame Oracle canned fortress.

(lambda (a b) (append a b)

η

>>1

This whole program looks like a suduko puzzle or something weird. How is anyone supposed to make sense of that?

>>20
by not being retarded.

>>1 (>>20-21)
What a fucking mess.

let rec change amt coins =
if amt < 1 then []
else [] |> List.fold_right List.append
(List.map (fun n ->
List.map (fun u -> n::u)
(change (amt - n) (List.filter (fun k -> k >= n) coins)))
coins)

The types are slightly different, but the LispScheme version relies on dynamic type coercions to overcomplicate everything. This code is still a mess.

Besides its use taking up a huge chunk of the run time I didn't get what >>19-sama was on about until I wrote this. See the usage of List.append, you can do that in Scheme too.

>>21
the only retarded person is the one that can't write clear readable code

>>22

thank you but it doesn't work

# #use "change2.ml";;
val change : int -> int list -> int list list = <fun>
# change 5 [1;2;5];;
- : int list list = []

I changed the first case to a [[]] and it still doesn't work:

# change 5 [1;2];;
- : int list list =
[[1; 1; 1; 1; 1]; [1; 1; 1; 1; 2]; [1; 1; 1; 2]; [1; 1; 2; 2]; [1; 2; 2];
[2; 2; 2]]

# change 1 [1;2];;
- : int list list = [[1]; [2]]

it's been a while since i touched the code but i think the <= 0 check was there for a reason that has to do with this

>>20
maybe i should use more descriptive names for the lambda bindings, then it would be much more readable

>>19
i was being a bit paranoid/stupid, append takes arbitrary amount of arguments so i wasn't sure i could use it with foldr which expects a function that takes exactly two arguments. but you're right, it works when i just do
...
(fold-right append
...

>>23

I'm really sorry. As I said, it was an exam question, so the code was written in a crazy adrenaline rush in like 5 minutes. If it were production I would use more descriptive variable names, and probably not do crazy hacks with 5 levels of nested HOFs. It was written for an university exam where you were given like 2 minutes to prove you weren't retarded. :/

so here is the lisp version with more descriptive variable names, and some comments:

(define (change amount coins)
(cond
((= amount 0) '(()))

;; `amount' can fall below zero on a recursion, which
;; means we have reached the full initial amount
;; and no further coins should be added

((or (<= amount 0) (null? coins)) '())
(else
(fold-right append
'()
(map
(lambda (coin-weight)
(map
(lambda (change-for-sub-amount)
(append (list coin-weight) change-for-sub-amount))

;; >= is to ensure we get results using only
;; sequences of coin-values that are increasing.
;; otherwise you will get repeats, e.g. (1 1 2)
;; and (2 1 1) both obtained for the same input problem

(change (- amount coin-weight)
(filter (lambda (k) (>= k coin-weight)) coins))))

coins)))))

What the fuck is this HtDP shit? Read your fucking SICP >>1-undergrad. No one cares about your damn variable names.

>>27

I have been reading SICP on and off for over 3 years now, also watched all the videos. I thought someone complained about the code being illegible, so I changed the variable names from single letters to verbose shit as above. Anyway, I appreciate your advice. do you have any other life advice for an undergrad, what should i do with my life, should I get fit, should I meet lots of people, whatever, well I am guessing a lot of people here are in their 30ies 40ies ?

>>28
Change majors. Don't do computer science.

>>29

why, is it because my code is shit or is it because it is a bad major to do? please give details. i think a lot about this stuff every day, what major i should do, etc. thank you

>>30
Your program text (plese don't call it code) will get better with time. It's probably good already. To be honest, what matters most about program text is:

How long does it take me to write it?
How long does it take me to make changes?
Is it executed efficiently enough?
How easily can I understand it tomorrow?
How easily can my friend understand it tomorrow?
How easily will I be able to run it in 10 years?

Change majors because programming for the sake of programming jobs suck, but programming in other fields is more fun.

>>31

Again, thank you very much for your advice. You seem to be hinting at valuing maintainability. As an undergrad fuckwit, this is something I am slowly starting to see the value of with my first two programming jobs where I did mostly maintenance. Fixing other people's bugs, adding features, etc.

I think Zed Shaw gives the same advice about programming in another field..

>>32
Yes but not imagined maintainability. Don't future program. Don't look at a problem and think "oh I'll make a library for this, and I'll make it super flexible so it can do this and this".

One of my first programming projects was a 3D game. I spent 2 months making a library for multiple OpenGL contexts in multiple Win32 or X windows in multiple threads. I never used this flexibility.

Other advice:

Don't be seduced by trends. Use old languages and old technology. The state of the art hasn't caught up to the 1980s yet, so you're not missing out on anything.

The best libraries are the libraries that haven't been updated for 10 years, and work with no hiccups after a trivial install.

An example of a trend id all this hooh-ah over dependent types - the example they like to point to is that you can have the length of a vector as part of the type. Well you could declare such a type in Common Lisp since CLtL1, and compilers like SBCL do something about it.

Another example is OpenGL. After spending the last 10 years butchering a nice high level API for 3D graphics we've wound up with some low level bullshit mixed with nonsensical abstractions. You need a team of >4 programmers to get anything done, and code bases end up huge. It's becoming a compilation target because it is no longer habitable. OpenGL 1.5, on the other hand, is absolutely beautiful, and an OpenGL 1.5 program reads like a book.

>>34

Interesting. I spent a lot of time reading about Lisp (SICP, PAIP) which is from like 1980-1990 but these guys seemed like total wizards and it seems like the world has indeed not caught up to them yet. I kind of like the C language too, should I pursue that? Pointers and structs seem like they can be quite elegant. They seemed to be pretty clever the Unix crew at Bell Labs

I have an opportunity to do OS development at Microsoft, idk if I should pursue that. Apparently it is quite a hectic job, dealing with race conditions etc. OS development seems like something a lot of people hate, when I took my undergrad OS course the class average was like 40% on the exam, and people were cursing the prof. Same goes for my undergraduate Java/OOP course I took, 39% class average and people hate the prof. I guess a lot of people go into CS because it's "cool" or "hot" or whatever and don't realize it takes a fair amount of dedication and skill and dealing with technical bullshit

I am slowly learning aobut how to try to be a good engineer. It seems if I get very fit I feel more empty and bliss and it becomes easier to memorize things, it seems a lot of this job is just memorizing things..

Be careful with learning languages. I wasted a lot of time on Haskell, only to have become a worse programmer. Same with C++.

I can't see how a regular person can master more than 3 programming languages in their lifetime, unless they devote their whole lives to programming, in which case you may be able to master 6. But you should not do this. By master I mean master - know the ins and outs of a number of existing implementations, be able to implement it yourself, know all the tools and libraries, know exactly how the language differs with it's siblings, be able to express anything written in any language in this one, have experience with the language in a wide number of contexts and so on. So choose wisely. You can dabble in many languages, but you can't master them.

Erik Naggum programmed in Common Lisp and Ada and had mastered C before that. This is a nice combination. I myself am currently mastering Common Lisp.

>>36
this is a lesson from someone with wisdom.

>>36

Mastering a language makes you a worse programmer? Is it because it restricts your way of thinking to the patterns of that language? Scheme and C seem to be the established classics. C# seems like a less verbose Java. MIPS assembly language seemed very very nice and well-designed. C++ seems very complicated. Python seems not so bad at times, at least for sneaky small tasks. Common Lisp sounds like a very complicated powerful language for crazy experts, but I always found it seemed less regular and well-designed than Scheme

This thread is full of idiots. To truly understand the difference between good and bad programming, you should study philosophy, specifically aesthetics, then disregard all those conclusions and come to your own. The experience you took to get the knowledge is still required though. Programming is just the mathematics of a process. A language is just a dumb grammar, and you'll realize that the goal is to make your program as weak as possible while still doing the job. Your hello-world should not be Turing complete. Why write f(x)=(x(x)-x)/x when all you need is f(x)=x+1? What I'm getting at here is that you need to achieve Satori. Also what I'm saying is, that I don't mean that everyone in this thread is an idiot. Actually, only >>36 is. Only a true idiot could manage to get worse by learning something new. If it makes you worse, then how bout you just not apply it, kay? But he's just some cocksuckick child molester, so don't listen to him and get back to your homework now.

>>24

thank you but it doesn't work

It has that defect, yes. I wrote >>22 to try to make sense of it, but that was before I saw >>2 so you can ignore me.

>>36
I don't know of any bigger waste of my time than to master any language according to that definition. To me, mastering the BNF description (of certain kinds of languages) is as good as mastering the language. Implementation quirks should either be standardized or removed from the language.

>>41

To me, mastering the BNF description (of certain kinds of languages) is as good as mastering the language

You're insane.

>>42
he probably means that most languages of the same type are only syntax-change from each other. this is sadly often the case.

>>42

The C grammar fits in like 2-3 pages IIRC in the K&R book. it's not *that* bad

>>1
c-c-cdr c-c-cdr c-c-cdr cdr cdr
c-c-cdr c-c-cdr c-c-cdr cdr cdr
c-c-cdr c-c-cdr c-c-cdr cdr cdr
c-c-cdr c-c-cdr c-c-cdr cdr cdr
c-c-cdr c-c-cdr c-c-cdr cdr cdr
c-c-cdr c-c-cdr c-c-cdr cdr cdr
c-c-cdr c-c-cdr c-c-cdr cdr cdr
c-c-cdr c-c-cdr c-c-cdr cdr cdr
c-c-cdr c-c-cdr c-c-cdr cdr cdr
c-c-cdr c-c-cdr c-c-cdr cdr cdr
c-c-cdr c-c-cdr c-c-cdr cdr cdr
c-c-cdr c-c-cdr c-c-cdr cdr cdr

>>41
I SAY WE STANDARDISE DA STANDARD, LET THE FAT CATS GET WHAT'S COMING TO THEM, YA FUCKIN STAK BOI RETOID

Lisp change machine? that's called a hammock my friend. Rich Hickey showed us the way. We need to join him and change lisp, and with it, the world.

>>47
kek

>>48
/polecat kebabs/

>>47
I made a change machine in Haskell with the Obama monad.

>>50
Well you failed, because it didn't give me the rest of my money back.