slipstream has quit [Read error: 110 (Connection timed out)]
Cygaaal has quit [Remote closed the connection]
joshcryer has quit [Connection reset by peer]
joshcryer has joined #ocaml
mordaunt has joined #ocaml
yminsky has quit []
jemfinch has joined #ocaml
mordaunt has quit [Read error: 104 (Connection reset by peer)]
<jemfinch>
I'm reading http://www.cs.cmu.edu/~neelk/rows.pdf about row polymorphism, and I'm having a bit of trouble understanding the notation. What does row.(r/a) mean? (it's used on page 7 and 21)
seafoodX has joined #ocaml
Smerdyakov has quit ["Leaving"]
mvitale has quit ["Leaving"]
buluca has quit [Read error: 113 (No route to host)]
<flux>
jonathanv, I think those claims (automatically multithreading) come only to life with purely functional languages (even if then)
bzzbzz has joined #ocaml
bla has quit [Read error: 110 (Connection timed out)]
bla has joined #ocaml
pantsd has joined #ocaml
thesoko has quit [Remote closed the connection]
thesoko has joined #ocaml
jlouis_ has joined #ocaml
jlouis has quit [Read error: 110 (Connection timed out)]
seafoodX has quit []
seafoodX has joined #ocaml
slipstream has joined #ocaml
slipstream-- has quit [Read error: 110 (Connection timed out)]
crabstick_ has joined #ocaml
crabstick has quit [Read error: 110 (Connection timed out)]
gaja has quit ["leaving"]
screwt892 has quit [Remote closed the connection]
gaja has joined #ocaml
Cygal has joined #ocaml
thesoko has quit [Remote closed the connection]
thesoko has joined #ocaml
buluca has joined #ocaml
smimou has joined #ocaml
pango has quit [Remote closed the connection]
pango has joined #ocaml
smimou has quit ["bli"]
buluca has quit [Remote closed the connection]
olegfink has quit [Read error: 104 (Connection reset by peer)]
olegfink has joined #ocaml
screwt8 has joined #ocaml
m3ga has joined #ocaml
pango has quit [Remote closed the connection]
pango has joined #ocaml
beno200 has joined #ocaml
beno200 has left #ocaml []
Demitar has quit [Read error: 113 (No route to host)]
screwt8 has quit [Read error: 104 (Connection reset by peer)]
thesoko has quit [Remote closed the connection]
thesoko has joined #ocaml
seafoodX has quit []
m3ga has quit ["disappearing into the sunset"]
seafoodX has joined #ocaml
seafoodX has quit [Client Quit]
netx has quit [Read error: 110 (Connection timed out)]
fremo has joined #ocaml
lde has joined #ocaml
screwt8 has joined #ocaml
smimou has joined #ocaml
rillig has joined #ocaml
Tetsuo has joined #ocaml
crabstick_ has quit []
seafoodX has joined #ocaml
jedai has joined #ocaml
|Jedai| has quit [Read error: 110 (Connection timed out)]
buluca has joined #ocaml
Smerdyakov has joined #ocaml
mbishop has quit [Read error: 110 (Connection timed out)]
smimou has quit ["bli"]
screwt8 has quit [Read error: 104 (Connection reset by peer)]
pango has quit [Remote closed the connection]
rillig_ has joined #ocaml
pango has joined #ocaml
rillig has quit [Read error: 110 (Connection timed out)]
screwt8 has joined #ocaml
bluestorm_ has joined #ocaml
bluestorm_ has quit [Remote closed the connection]
buluca has quit [Read error: 113 (No route to host)]
szsz has quit [Read error: 104 (Connection reset by peer)]
pango has quit [Remote closed the connection]
rillig_ is now known as rillig
smimou has joined #ocaml
pango has joined #ocaml
pango has quit [Remote closed the connection]
smimou has quit ["bli"]
pango has joined #ocaml
<flux>
does anyone know of a (the name of a) program/algorithm that solves this kind of problem:
<flux>
I have a set of university classes, which each have one exercise per week, from a set of exercise times for that course
<danderson>
scheduling algorithms?
<flux>
and I would like to find the best set of exercises, judged by a certain goodness-function
<danderson>
NP-complete problem
<flux>
sudoku is np-complete, no?
<flux>
it doesn't mean it cannot be solved for a limited number of cases
<danderson>
maybe, but scheduling is NP-complete and hard for even relatively simple cases
<danderson>
I don't know of any exact solutions other than brute force
<flux>
I'd like to find a set of classes so that I enter the school once a day and get off once, leaving continuous time spans of free time or university time
<Smerdyakov>
Try using an integer linear programming package.
<flux>
hmm
<danderson>
heuristic solutions that we tried for a similar assignment included genetic algorithms, simulated annealing, and an agent-based approach, where each selection is an independant agent trying to move to its lowest energy state
<danderson>
all work out fairly well for simple cases. If you are trying to assign only for 1 student, with no per-class cap and predefined times, I think you'd reach an optimum fairly quickly.
<flux>
yes, 1 student, me :-)
<flux>
perhaps even brute force would be ok
<flux>
it would give me pretty free hands on deciding the goodness-function
<danderson>
(we were given class timetables for all courses, the list of courses chosen by N students, and per-class caps on each timeslot, with the objective of producing N student timetables with minimal conflicts)
<danderson>
(and that is hard.)
<danderson>
the next year even got to decide when the classes should be, based on teacher availability timetables.
<Smerdyakov>
The point of using an ILP package is that you leave it up to the package's implementers to decide _how_ to solve the problem. You just describe individual instances declaratively.
<flux>
smerdyakov, do you know a name of such a package?
<danderson>
right, if your problem can be experessed in that form
<flux>
I'm wondering if it might still be faster to write (and run) a brute-force algo with ocaml than study how such a package is used :)
<danderson>
which is, afaik, not the case for looser scheduling problems. You might get away with it for the subset you're after.
<Smerdyakov>
danderson, any NP-complete problem's instances can all be expressed in that form, and you already said that this is NP-complete.
<danderson>
I see. I'm curious then why getting timetabling right is still an open problem, if any ILP package is already the best you can do
<flux>
apparently matlab might have such a tool
<flux>
now all I need to figure out is how to express the problem to it..
<Smerdyakov>
flux, no, I've never used an ILP solver and can't recommend any by name.
<flux>
(after I've found a host with matlab from uni)
<Smerdyakov>
danderson, who said it was the best you can do?
<danderson>
you seemed to imply that, by recommending it over other approaches. My mistake if that was not the implication.
<Smerdyakov>
danderson, flux has said that he has only simple problem instances, so I don't expect performance to be a program for _any_ choice. Thus, I recommended the approach that would get results soonest.
<Smerdyakov>
s/to be a program/to be a problem
<danderson>
I see.
<flux>
hooray, I found a host with matlab/linprog
<flux>
now I just need to study what the algorithm solves to formulate my problem to it..
<Smerdyakov>
flux, it's easy to find open source ILP solvers with a web search.
screwt8 has quit [Remote closed the connection]
bluestorm_ has joined #ocaml
screwt8 has joined #ocaml
gunark has quit [Client Quit]
gunark has joined #ocaml
seafoodX has quit []
mbishop has joined #ocaml
bluestorm_ has quit [Remote closed the connection]
psnively has joined #ocaml
aij has quit [Remote closed the connection]
Demitar has joined #ocaml
aij has joined #ocaml
Tetsuo has quit ["Leaving"]
TFK has joined #ocaml
jlouis has joined #ocaml
jlouis_ has quit [Read error: 110 (Connection timed out)]
psnively has quit []
Cygal has quit [Remote closed the connection]
Cygal has joined #ocaml
yakker has joined #ocaml
<yakker>
is the @ operator to append an element to a list a constant time one?
<yakker>
mylist:=!mylist@[newelt]
<jemfinch>
no
<jemfinch>
it's O(n) in the size of the list
<yakker>
for some reason, my program, which uses this for the order of a few thousand elements completely stalls when I use it
<jemfinch>
of course it does
<yakker>
jemfinch, yeesh, ok now I know
<yakker>
what about :: ?
<jemfinch>
constant time
<yakker>
so lists aren't doubly linked?
<jemfinch>
yakker: no, lists are standard functional lists
<jemfinch>
it's not easy (if it's possible at all) to implement doubly linked functional lists.
<yakker>
jemfinch, hm, so pairs of pairs of pairs of pairs of pairs ?
<jemfinch>
yakker: your question doesn't make sense
<jemfinch>
you can, of course, have pairs of pairs of pairs of pairs if for some strange reason you want them.
<jemfinch>
but that's entirely irrelevent to the implementation of functional, doubly-linked lists.
<jonathanv>
how do you get the head and rest of a list without doing pattern matching?
<yakker>
ok, my question was if 'standard functional lists'
<yakker>
are built out of pairs
<jemfinch>
jonathanv: if you need both, do pattern matching.
<jonathanv>
hmm
<jemfinch>
jonathanv: if you need one or the other, use List.hd or List.tl (iirc the OCaml incantations)
<jemfinch>
yakker: lists are just a simple datatype: type 'a list = Cons of 'a * 'a list | Nil
<jonathanv>
okay
<yakker>
ok, so that's a pair.
<jonathanv>
thanks
<jemfinch>
yakker: yup, basically.
<jemfinch>
yakker: I'm pretty sure doubly-linked lists would of necessity involve mutable cells (or, at least, mutable forward pointers)
<jemfinch>
yakker: in which case they cease to be functional
<jemfinch>
now's my turn to ask a question: does anyone know of a document that documents how classes (i.e., extensible records) are implemented? I.e., what form they take in memory
<yakker>
jemfinch, ya, to get to the tail, you need a tail ref
olegfink has quit [Read error: 101 (Network is unreachable)]