<gim_>
:: is said to be a "keyword" not an operator ...
<gim_>
but in fact it's the same for +
mpc has joined #ocaml
gim_ has quit ["dodo"]
keenan has quit ["I'm a quit message virus. Please copy me into your own quit message, and change me as you see fit, so I may spread and evolve]
mpc has quit []
srv_ has quit [Read error: 104 (Connection reset by peer)]
srv has joined #ocaml
zigong_ has quit ["Leaving"]
karryall has quit [Ping timeout: 14400 seconds]
karryall has joined #ocaml
alex-i has joined #ocaml
afx has quit [Remote closed the connection]
monochrom has joined #ocaml
mpc has joined #ocaml
mpc has quit [Client Quit]
GreyLensman has quit ["Leaving"]
zigong__ has joined #ocaml
mrsolo has joined #ocaml
Anvil_Vapre has quit ["Leaving"]
Exquisite_Corpse has joined #ocaml
Exquisite_Corpse has quit ["Leaving"]
Anvil_Vapre has joined #ocaml
cjohnson has quit ["Leaving"]
monochrom has quit ["Don't talk to those who talk to themselves."]
afx has joined #ocaml
Hadaka has quit [Read error: 60 (Operation timed out)]
Naked has joined #ocaml
Naked is now known as Hadaka
pango has quit ["Client exiting"]
pango has joined #ocaml
mlh has quit ["who are you people and what are you doing in my computer!?"]
mlh has joined #ocaml
cmeme has quit ["Client terminated by server"]
cmeme has joined #ocaml
Herrchen has joined #ocaml
kinners has joined #ocaml
Herrchen has quit [Client Quit]
Herrchen has joined #ocaml
vezenchio has joined #ocaml
kinners has quit [Read error: 110 (Connection timed out)]
gim has joined #ocaml
afx has quit ["Leaving"]
docelic has quit ["Quit"]
cjohnson has joined #ocaml
pango is now known as pangoafk
bk_ has quit ["Leaving IRC - dircproxy 1.1.0"]
Iter has joined #ocaml
mlh has quit [Client Quit]
mlh has joined #ocaml
Anvil_Vapre has quit ["Leaving"]
cjohnson has quit ["Leaving"]
karryall has quit [Read error: 110 (Connection timed out)]
Lemmih is now known as Lemmih|Unicyclin
mlh has quit ["ni!"]
pangoafk is now known as pango
Lemmih|Unicyclin is now known as Lemmih
mrsolo has quit [Read error: 113 (No route to host)]
Herrchen has quit ["bye"]
<jason__>
Hm, is there a memory efficient way of building a significantly long List?
<jason__>
I'm trying to read in a 41000 element array.
<Riastradh>
Do you know beforehand how big the array is?
<jason__>
Well, yes, but I'd like to avoid knowing that.
<jason__>
If at all possible.
<jason__>
vector template works just fine in C++ because it redoubles the size of the memory in the background.
<Riastradh>
Lists aren't very memory-efficient in the first place.
<jason__>
But, I was trying to use a recursive method, and of course a copy of the List at every element exists on the heap.
<jason__>
So, I think I may need to use something mutable.
<Riastradh>
A copy?
<Riastradh>
Where do you get that idea?
<jason__>
Doesn't it?
<jason__>
Like, I pass the List with the added next element read to the file back into the method recursively.
<jason__>
Ahem, from the file.
<Riastradh>
Are you talking about doing something like 'accum @ [newelt]' at every iteration?
<jason__>
List.append.
<Riastradh>
That is the worst way to build up a list.
<jason__>
Lol, yeah, I figured it might be :p
<Riastradh>
You should either do it tail-recursively in reverse, or non-tail-recursively.
<jason__>
So, wait a sec, I read an element from the list every time my function is called.
<Riastradh>
What do you mean 'read an element from the list?'
<jason__>
From the file.
<jason__>
Sorry.
<jason__>
Hehe.
<Riastradh>
OK...
<jason__>
And then I want to append it to a List in an efficient manner.
<Riastradh>
No, don't append it to the end.
<Riastradh>
Either add it to the beginning and at the end of the loop reverse the accumulated list, or build it up non-tail-recursively.
<Banana>
jason__: put the element at the begining and reverse the list at the end...
<jason__>
Well, just a second, when I pass the array back into the function, how does Ocaml handle that? Does it copy the list?
<Riastradh>
The 'array?'
<jason__>
The List.
<jason__>
Damnit.
<jason__>
Lol.
<Riastradh>
And pass it to what function?
<jason__>
Into the recursive function.
<Banana>
jason__: if you use a list [1;2;3] it doesn't copy the whole list on the stack.
<Banana>
only a pointer to the begining of the list.
<jason__>
Hm.
<jason__>
So, when I pass it, it's by pointer then.
<Banana>
well, it's a value.
<Banana>
but internally, ocaml represent it as a pointer.
<Banana>
the fact is that a list is a persistant data structure so you cannot modify it "in place".
<jason__>
Alright.
<Riastradh>
OCaml is a call-by-value language, _not_ call-by-copy.
<jason__>
Right.
<jason__>
How does it maintain the background immutable value though?
lmbdwar has left #ocaml []
<jason__>
Like, when I recursively call my function, what if I manipulate that same value after the function returns?
<Riastradh>
You're talking in generalities that I can't really answer.
<jason__>
Will it be the value that was manipulated by the above context? Or will it be preseved?
<Banana>
jason__: the only way you have to manipulate a list is to use pattern matching (i mean atomically)
<Banana>
like match l with [] -> ... | p::r -> ...
<jason__>
Yeah.
<jason__>
Okay, I'll see about adding the element to the front of the list.
<Banana>
so you deconstruct your list and do what ever you want with it. but when you use p and r to build something like (p,r) as result of your function then the old list is still p::r
<Banana>
i don't know if i'm clear...
<Banana>
i think i am not.
<Banana>
:/
maeglin has joined #ocaml
<Banana>
well anyway as long as you don't uses references or arrays, (or mutable field in records) then you don't have to worry about "old" values.
<Banana>
they are always preserved.
<jason__>
Yeah, but how?
<jason__>
I'll have to read more about the underlying implementation of things :) Heh.
<pango>
jason__: each element of a list has a pointer to the next; each element is immutable, so all you can do is create new lists, that may share their tail with other lists
<jason__>
.. Oh.. Okay.
<jason__>
So, the previous recursive call will have a list that is looking at a segment of the underlying background list?
<pango>
jason__: that's why lists are asymetric, and it's much more efficient to make changes near their head
<Riastradh>
You shouldn't care about the underlying implementation of things.
<jason__>
Right, because you don't have to keep figuring out the length.
<jason__>
Okay.
<jason__>
Riastradh: It usually helps in making your programs operate efficiently.
<pango>
jason__: because you don't have to create a copy of the whole list
<Riastradh>
This is an unfortunately common pitfall.
<jason__>
Oh.
<jason__>
Shit.
<jason__>
How do I know when my file has finished otherwise?
<Riastradh>
You need to surround the input_line with a try/with expression.
<Riastradh>
This auxiliary may help:
<Riastradh>
let maybe_input_line channel =
<Riastradh>
try Some (input_line channel)
<Riastradh>
with End_of_file -> None
<Riastradh>
Then match the result of maybe_input_line, conditionally proceeding.
<Riastradh>
By the way, you could also simplify parsing the result of Str.split by doing:
<Riastradh>
let [binX; binY; binZ] = Str.split dataParser input in
<jason__>
Ah, very cool.
<jason__>
I should have thought of that :p
<pango>
and x, y, z scream "records!" or at least "tuples" :)
<pango>
as I guess you'll keep manipulating them together
<jason__>
Let me take things a step at a time here :P Hehe.
<jason__>
Riastradh: So, None is () right?
<Riastradh>
Uh, no, None is None.
<jason__>
Heh, so match with None -> return my lists?
<Riastradh>
Yes.
<jason__>
Got it.
pango has quit ["brb"]
maeglin has left #ocaml []
pango has joined #ocaml
<jason__>
Grr. How do you use try and in? I'm doing let myFunc = try <statement with <Returnval> in
<Riastradh>
Surround it with parentheses.
Banana_ has joined #ocaml
Banana has quit [Read error: 110 (Connection timed out)]
Rikola has joined #ocaml
cjohnson has joined #ocaml
Banana has joined #ocaml
Banana_ has quit [Read error: 104 (Connection reset by peer)]
CosmicRay has joined #ocaml
Rikola has quit []
<Hadaka>
gah how I hate mapping, traversing and modifying lists and trees - you don't want to do it with recursion gobbling up stack space for intermediate compositions - and you don't want to build everything backwards and reverse it at the end...
<Riastradh>
The stack should just be managed better and copied to the heap on overflow.
<Smerdyakov>
No. It should call the RAM company and wait for installation of new units.
CosmicRay has quit ["Client exiting"]
<Hadaka>
well, even just special handling of tail variant composing would be nice
<Hadaka>
I mean, it can nuke everything but the actual last data to be returned from the stack frame
<Riastradh>
...?
<Hadaka>
if that would work, then even the naive implementation of List.append would be efficient
<Riastradh>
Define 'efficient.'
<Riastradh>
Does it make a difference whether you accumulate intermediate storage in the stack or the heap?
<Hadaka>
not croaking on stack space and not keeping the entire stack frame of the function on stack
<Riastradh>
The only problem with non-tail-recursive list processing is that the stack is limited in size, and that size tends to be small.
<Hadaka>
and the fact that you use up space proportional to the size of the stack frame for the function in question, even if none of it is used in the end
bk_ has joined #ocaml
* vincenz
has a question on how frames are created in ocaml and other fpl
<vincenz>
but the how is it decided what goes into the frame...which variables...obviously not all as that's overkill
<vincenz>
for example
<vincenz>
let f _ = let a = 2 in (fun x -> a + x)
<vincenz>
let f _ = let a = 2 in let b = 3 in (fun x -> a + x)
<Hadaka>
pango: yes, that's exactly what I was doing a while ago :)
<vincenz>
obviously only the a should be saved
<vincenz>
you're still creating a 'stack'
<vincenz>
the stack of functions to rturn
<pango>
but it's not on the stack
<vincenz>
best way to ensure non-blowop is tail-call-optimizatin
<vincenz>
pango: sure it is...you create a bigger and bigger function (a 'stack' of fucntions, note I use the term lightly)
<Hadaka>
vincenz: if you want to really know what's going on, make that code - and compile it with -dinstr - then you'll see in the bytecode exactly what's called and when
<vincenz>
Hadaka: you're building a bigger and bigger function on the hea
<vincenz>
what you save on the stack you expend on the heap
<Hadaka>
vincenz: err, the function doesn't grow, new closure objects with variables are created though
<vincenz>
well yes...but you create n functions for len(l1) == n
<vincenz>
so you're still wasting space
<Hadaka>
wasting compared to what?
<vincenz>
tail-call optimization
<Hadaka>
well how would you tail-call optimize List.append for example?
<Hadaka>
so what you are doing is List.rev combined with List.rev_append
<Hadaka>
yes?
<vincenz>
yup
<vincenz>
cost = O(2*len(l1))
<vincenz>
and it's tail-call optimized
<vincenz>
both are
<Hadaka>
yes, so you trade processing time for stack space? that's not acceptable
<vincenz>
sure it is
<vincenz>
I don't have to run through a whole bunch of functiosn like your solution
<vincenz>
in the end the proecssing time is the same
<vincenz>
you have to call len(l1) functions on exiting
<vincenz>
so I actually believe my solution is faster
<vincenz>
less jumping through the heap
<Hadaka>
yeah, the function composition produces the result of List.rev more or less
* vincenz
nods
<vincenz>
without the space overhead
<Hadaka>
but the reason I did it with function composition was that my thing wasn't a list, but a branching tree - so it was really hard to make a 'reverse' operation for it
<Hadaka>
but!
<Hadaka>
there is no need to pay the stack size price, or the processing time price
<vincenz>
oh?
<Hadaka>
this is just a problem of ocaml as a language that this is difficult
<vincenz>
not really. any fpl lang will have the same issues
<vincenz>
unless you can work on the internals
<vincenz>
any single-directed linked list has the same issues in fact
<vincenz>
whatever the lang
<vincenz>
unless you can rip it open and mess with the internals
<Hadaka>
yes, but tail value composition could be optimized to have only the storage cost of the elements
<Hadaka>
whether the elements are stored on stack or heap is irrelevant, if stack can be infinite
<vincenz>
my solution onl has the storage cost of the elements
<Hadaka>
yes, but increased processing cost
<vincenz>
how?
<vincenz>
what I spend in the list_reverse, you spend in the func-calls
<Hadaka>
forget the func calls
<vincenz>
you're just moving it elsewhere
<Hadaka>
just think about a normal List.append
<vincenz>
I assume it's written in c, goes to the end of l1 and makes it point to l2
<vincenz>
aka, you're ripping open the internals
<Hadaka>
nono, I meant a naive List.append
<pango>
Hadaka: you need a different datastructure than immutable single linked lists, that's all...
<vincenz>
Hadaka: its' a given that any single linked list will have the same computation cost
<vincenz>
whether you put that in multiple returns, a function-call composition, or a list_reverse
<vincenz>
you're just moving the problem to somewhere less visible
<pango>
Hadaka: the problem is you lose the simplicity of the syntax when you do so :(
<vincenz>
it's a computational given
<vincenz>
but I do think that function-call composition will have more effective overhead as you haev to jump over the heap to all the functions
<vincenz>
but that's one of those factors pure CS people don't take into account
<pango>
vincenz: forget function calls, it was just a work around stack limit
<vincenz>
which in the EE world is very important
<Hadaka>
let append l = function
<Hadaka>
| h :: t -> h :: (append l t)
<Hadaka>
| [] -> t
<vincenz>
pango: yes, you're moving it to the heap.... my solution solves that
<Hadaka>
um, didn't write that exactly correct, but anyway
<vincenz>
my point is simple, the computational overhead in O notation is the same for all three solutions
<vincenz>
one uses stack space, one heap space, and one no extra space
<vincenz>
you have the 2*len(l1) in each solution
* vincenz
shrugs
<Hadaka>
why would that example have 2*len(l1) as the cost? it calls one function per element?
<vincenz>
coming from an EE/optimization background I know my solution is the most efficient
<vincenz>
Hadaka: you have to move back up the stack at the end
<vincenz>
the cost in your case is just less visible
<vincenz>
but it's nonetheless there
<Hadaka>
hmmh, yeah, actually, you are right, it does have to move back up the stack at the end
<vincenz>
that's the problem with typical O notation
<vincenz>
it fails to see many issues
<vincenz>
and even if you didn't have to move back up the stack, you're still doing constant*len(l1) operations, the question is: which will be most efficient
<Hadaka>
but, I still believe it would be possible to special case function return being a variant composition, and internally handle composing the values without traversing the stack frame back up
<vincenz>
what's a 'variant composition'?
<Hadaka>
well h :: t, or Node (value, left, right), or whatever
<jason__>
In order to make a string either be None or a value, do I have to define a type? Like "type val = StrVal of string | None;"?
<vincenz>
Hadaka: no matter how broad or how specific you go, unless you rip open the internals, the computation-cost is a given for this problem, it's inherent
<jason__>
Or is there already something standard for doing this?
<vincenz>
jason__: that already exists: string option
<Hadaka>
jason__: the option type
<pango>
jason__: 'a option
<jason__>
So, when I return a string from my function what do I construct it with?
<vincenz>
type 'a option = None | Some of 'a;
<jason__>
Like, I tried doing a function that either returned a string, or None,.
<vincenz>
jason__: return either None or (Some "string")
<jason__>
Okay, so return "Some myString"?
<jason__>
Got it.
<jason__>
Then match on Some.
<Hadaka>
vincenz: 'rip open the internals' is a bit of an odd proposition if we are talking about how the ocaml compiler (or runtime) could possibly do that
<Hadaka>
yes, it is internals, if it's ocaml which would do it interally
<vincenz>
Hadaka: well the compiler has access to the internals...a linke dlist is typically a record of [value, pointertonext]
m3ga has joined #ocaml
<Hadaka>
the compiler *is* the internals :)
<vincenz>
basically...write List.append in c and not in ocaml
<vincenz>
you get access to the "next pointer"
<pango>
Hadaka: you're thinking of some Lisps, that allow to modify the car and the cdr or lists ?
<pango>
s/or/of/
<vincenz>
that would screw with the typing systme I think
<pango>
that wouldn't be immutable lists anymore...
<Hadaka>
what I am talking is a generic solution for the compiler to optimize functions which return variants at the tail, just like tail-call optimization is done
<Hadaka>
yeah, I know it can be done for datatypes by hand (with C or Obj.magic)
<vincenz>
Hadaka: that's only possible if the compiler knows the internals, and it may not always be such a simple case
<pango>
Hadaka: since they wouldn't be immutable anymore, and yet would have to behave like immutable lists, you would have to be very careful that it doesn't show ;)
<vincenz>
for specific cases, perhaps
<Hadaka>
vincenz: eh? how could the compiler not know the internals if it is compiling the code
m3ga has left #ocaml []
<vincenz>
Hadaka: I just mean that for more complex cases it would not be feasible
<Hadaka>
pango: I wasn't thinking about allowing mutable lists, just that their composition could be mutable
<vincenz>
if I wre a genius I could probably give you a proof and equate it to the halting problem
<pango>
Hadaka: same thing, if the composition is mutable, the list is
<Hadaka>
you think it ends up being impossible?
<vincenz>
Hadaka: the compiler deciding whether to remoev the stack crap and such for a general function? yes
<Hadaka>
pango: now if the mutably composed values never escape anywhere until the list is finished
<Hadaka>
hmh
<pango>
Hadaka: if you can mute the composition, you cannot share the list with code that don't expect the list to change under them
<Hadaka>
pango: the resulting datatypes would obviously not be mutable, hence no problem
<Hadaka>
hell, I bet extlib...
* vincenz
had a very strange type-problem with a piece of code he wrote
<Hadaka>
heh:
<Hadaka>
type 'a mut_list = {
<Hadaka>
hd: 'a;
<Hadaka>
mutable tl: 'a list
<Hadaka>
}
<Hadaka>
extlib does List.append by playing around with Obj.magic
<vincenz>
Hadaka: euhm....you couldn't build recursive funcs....tl is not of type 'a mut_list
<pango>
Hadaka: mutable tl: 'a mut_list I guess
<vincenz>
what pango said
<Hadaka>
pango: no
<Hadaka>
I'll put the code in a pastebin
<vincenz>
of course Hadaka
<vincenz>
type of l = 'a mut_list
<vincenz>
type of tail a = 'a list
<Riastradh>
I've returned late to the conversation. Can someone give me a quick overview of what the currently contended point is, so I can beat you both into submission with my superior intellect?
<jason__>
let [a;b;c;d;e;f] = Str.split myReg myStr, claims the pattern matching isn't exhaustive.
<Riastradh>
jason__, you probably want to use match, though, not let.
<vincenz>
Riastradh: mind taking a look at a piece of code?
<vincenz>
I have a typing issue
<jason__>
Riastradh, well, I want to split it up into elements, but how do I handle the case that it may be []?
<Riastradh>
With match.
<jason__>
In a let statement?
<Riastradh>
match Str.split ... with
<Riastradh>
[] -> ...
<vincenz>
Hadaka: you sick sick man
<jason__>
Okay, thats what I wanted to know.
<jason__>
Thanks :p
<Riastradh>
| (x:xs) -> ...
<jason__>
Is it safe not to check for that?
<jason__>
Or should I always make sure to check for []?
<vincenz>
jason__: always make sure to check all possibilities, if it's something you don't want just make it raise an exception
<Hadaka>
Riastradh: do you think it'd be possible for the ocaml compiler to optimize cases where recursive functions return variants like h :: t or Node (value, left, right) so that their composition would not require additional stack space, heap space or processing time over what's internal to the operations? ;)
<Hadaka>
vincenz: that wasn't my code, it's a part of Extlib - they have versions of just about every List function written that way
<vincenz>
they're sick :P
<vincenz>
anyone ever play around with mod_caml?
<Riastradh>
vincenz, oh, yes, go ahead, paste the code; I'll look at it.
<vincenz>
I got it to compile and install (after installing Pcre and findlib) but when I launch APache, apache won't launch
* vincenz
wishes paste had coloring for ocaml
<Riastradh>
Hadaka, no.
<Riastradh>
You're asking for temporary storage not to exist.
<vincenz>
Riastradh: it's quite a piece ... let me paste the code and then explain what breaks ti?
<Riastradh>
That is, for magically nonexistent temporary storage -- a place to store a stack without occupying any memory.
<Hadaka>
Riastradh: err, no, obviously the elements have to be stored somewhere
<Riastradh>
Right.
<Hadaka>
Riastradh: what I mean is that there would be no need to backtrack the stack or functions at the end
<vincenz>
Riastradh: list_append is an exception, you can reverse the first list in space and then append in space
<Hadaka>
Riastradh: and there would be no need to reverse a list at the end
<vincenz>
Hadaka: trust me...for more complex problems it becomes uncompileable
<Riastradh>
Reversing the list is just the same as unwinding the stack.
<Riastradh>
Only it occurs on the heap, not on the stack, but really, the stack is just a part of the heap that tends to stay in the cache.
<vincenz>
Riastradh: it can be done in place...reverse first list with tail-call optimization....and then append reversed list to second list
<Hadaka>
but if we do it with mutable lists, then there's no need to walk back at all
<vincenz>
Hadaka: yes but the advantage of immutable things is pure-functional programming
<jason__>
It's really convenient to say [binX;binY;binZ] = Str.split :P Now I have to match each element out with another match.
<vincenz>
lemme explain... the type of match_context is
<Hadaka>
vincenz: no, but the values wouldn't have to be mutable after they have been composed
<vincenz>
string list list -> (string list -> string list list -> 'c) -> 'c
<vincenz>
if I make this explict
<Riastradh>
Hadaka, the way you have distorted your code to use mutable lists is _far_ more drastic than you might think.
<vincenz>
then iter_all makes the 'c become unit
<vincenz>
and then find_context becomes ->unit instead of -> 'a ('a is the value-type of the hashmap)
<Hadaka>
Riastradh: I haven't distorted any code - the code that I pasted was from Extlib - and what I'm proposing is that the compiler does the distortion and keeps it there, so it cannot spill over
<vincenz>
aka the 'c gets bound i fI make the type of match_context exlpict
<Riastradh>
Hadaka, the problem is that the difference between the original code and the imperative code is _huge_.
<Hadaka>
anyhow, nevermind me as long as somebody has an actual problem with his code
<Hadaka>
I'm just wondering these things
<Riastradh>
It doesn't matter that it won't spill over; it's just _dramatically_ different.
<vincenz>
Hadaka: if the lists were mutable...you'd have to clone l2 first....cause you can't make the appended list just point to it
<Hadaka>
Riastradh: why would the code need to be different? what I'm talking about is for the compiler to *optimize* value composition in recursive functions, just like it optimizes tail-calls (well, not just like, but in a bit of a similar manner)
<Hadaka>
once again, I'm not talking about having mutable lists in general
<Riastradh>
Hadaka, yes, I know what you're talking about.
<Riastradh>
I'm saying that that optimizing transformation is incredibly non-trivial.
<Hadaka>
Riastradh: okay, then I believe you do :)
<vincenz>
Hadaka: that optimization is a halting problem in the general case...only in speecific cases like List.append is it computable
<vincenz>
Hadaka: and for those cases...just write the code in c
<Hadaka>
well, I will keep thinking about this, thank you for your insight and expertese, both of you
<jason__>
Riastradh: Okay, this is is a heck of a lot faster, thanks :)
<vincenz>
Riastradh: any ideas why making the match_context explict binds the output type?
<Riastradh>
Nope.
<vincenz>
maybe cause when I create an object it gets instantiated and the type becomes '_c ?
<vincenz>
though you'd figure that would be true as well when it's not explicitly typed
<vincenz>
anyone that has used mod_caml?
alex-i has quit ["leaving"]
<jason__>
Man, it's lightning fast native compiled.
<jason__>
Very very nice :)
<jason__>
Takes it like, half a second to parse and pack three arrays of 41000 points.
<jason__>
Riastradh: What's a good way to reverse the list?
<jason__>
Riastradh: Is there a library routine to do this?
<pango>
List.rev
<jason__>
Ah, yeah, just saw that.
<jason__>
Thanks :)
mlh has joined #ocaml
<jason__>
Is there any way to load a .ml file from the interpreter?
<jason__>
I really like that the compiler informs you of open-ends in your program.
<vincenz>
Anyone know a pcre lib that does not use the native libpcre
<vincenz>
You'll need mod_caml 1.0.6 or above and Apache 1.3. (Apache 2.0 seems to be incompatible with modules that use recent versions of PCRE.) -- damned, it was mentioned somewhere