<ayrnieu>
I'm surprised that this doesn't already exist...
<ayrnieu>
anyway, what question do you have?
<Smirnov>
I just want it to be O(n) I guess
<ayrnieu>
Sure; anything else would be a bug.
<Smirnov>
actually I probably need fold_right to do that dont I?
<Smirnov>
otherwise my list would get reversed
<ayrnieu>
I wouldn't bother with fold for this, but why don't you implement it and see?
_fab has quit [Read error: 113 (No route to host)]
<Smirnov>
cause fold is the it thing
<ayrnieu>
the 'it thing'? eh, OK.
<Smirnov>
everyone is hyped about fold
<Smirnov>
fold left, fold right, down the middle, etc
<ayrnieu>
I wouldn't bother with it anyway. but why don't you implement your version that uses fold_right and see if it works?
<Smirnov>
bother with what?
<ayrnieu>
with using fold. For this.
<Smirnov>
ah
<Smirnov>
well actually i need to return a tuple (bool,min,[list-without-first-occurance-of-min])
<Smirnov>
but i couldnt figure out an O(n) way to do it in one pass , so I'm getting the min first, and then getting the list
<ayrnieu>
oh, you want to find the lowest value in a list of numbers, and then remove the first occurence of that value from the list? Yes, you'll need O(2n).
<Smirnov>
ok good
<Smirnov>
i thought i was going nuts
<Smirnov>
:P
<Smirnov>
I could do it in O(n) in C i think
<Smirnov>
but someone just had a bright idea to make @ O(n)
_fab has joined #ocaml
<gmh33>
just out of curiousity, is there a somewhat simple way to achieve real time concurrency in OCaml?
<ayrnieu>
an O(n) way to do this is to assume that each member of the list might be the min as you come across it, optimistically constructing the list that removes that element right there, and then continuing with this until its guess is disabused.
<ayrnieu>
gmh - please don't say 'real time'; that's a very tough question with increasingly hard-science methodology as you try to more fully answer it. Let's say that you asked "Can I write O'Caml programs an a concurrency-oriented manner?"
<gmh33>
ayrnieu - the question is in my head from reading on the OCaml page. It said a concurrency-oriented style can be achieved but the implimentation is achieved by running a bit of one piece then a bit of the other back and forth
<gmh33>
I thought it'd make a smidge of difference in terms of run time performance
<ayrnieu>
what you described would apply just as well to Erlang.
<gmh33>
is that how Erlang impliments concurrency?
<Smirnov>
ayrnieu: but reconstructing a list is O(n) isnt it :)
<ayrnieu>
gmh - that question is really painful, you know.
<Smirnov>
thus if you run it on the list of [1;2;3;4;5;6] you would get O(n^2)
<gmh33>
ayrnieu - fair enough
<gmh33>
oh well I have to go, thanks for your insite :D
<ayrnieu>
gmh - Erlang's task-switching logic does also look at 'reductions', a simple count of function-applications per process.
<Smirnov>
bloody hell
<Smirnov>
using fold_right removes it from the right
<ayrnieu>
Smirnov - you always maintain the list-so-far, and the list-to-go, and when you test that the current element is less-than-the-previous-min, you can just pass a {list-so-far,list-to-go} tuple, dropping the current element. When you reach the end, if the current element is the new min, you just return the maintained list-so-far; otherwise, you extract {list-so-far,list-to-go} from the tuple and return their concatena
<ayrnieu>
tion.
<Smirnov>
dropping the current element from where
chessguy has quit [Read error: 104 (Connection reset by peer)]
<ayrnieu>
smirnov - you don't actually do a 'dropping operation'; you've already pattern-matched it out, and just don't add it back in when you pass the new tuple on the recursive call. You'll still push it to the front of list-so-far for subsequent operation. This is all false, anyway, since you'll need to reverse that list at some point.
<Smirnov>
.... so what you said does not hold?
<ayrnieu>
when I said what?
<Smirnov>
" This is all false, anyway, since you'll need to reverse that list at some point."
<ayrnieu>
*oh*, I told you that I had a O(n) way to do this. Sorry!
<Smirnov>
So you don't?
<ayrnieu>
No; I've described a one-pass solution, but it still uses List.reverse
<Smirnov>
ok
<Smirnov>
so its not one pass lol
<ayrnieu>
call it O(N+(N-k)+k) , where k is the length of the final list-so-far when you reverse and again when you append list-to-go
<Smirnov>
if its not one pass, i can make it 2 or 3, not a big deal
<ayrnieu>
although that final +k isn't necessary, with a List.reverse that also returns the last cons of the list.
<ayrnieu>
O(N+(N-k)) ! Clearly the optimal solution! Not-quite-two-full-passes.
<Smirnov>
which is still O(N) in the end isnt it?
<Smirnov>
anyway i just needed something better than O(n^2)
<ayrnieu>
Well, I just gave you O(N+N-k), which is only O(2N) in the perverse case of the min being at the very end of the list, which is certainly better than O(N^2)
<ayrnieu>
although if that's all you want, search for the min in one pass and remove it in the other.
<Smirnov>
you told me a lot of very complex sounding things and mentioned that something was all false anyways
<ayrnieu>
You're a very skeptical person, you know that? :-)
<Smirnov>
i was trying to understand your solution and then you mentioned it was flawed and that got me completely stumped
<ayrnieu>
oh, I just meant that it wasn't O(N)
<Smirnov>
was that a solution for the entire 3 element tuple i need to ultimately return or just for taking the min out of the list?
<ayrnieu>
that can return the second and third elements you need, although I don't know what you want with the bool
<Smirnov>
is list_so_far @ min_so_far @ list_to_go ... supposed to be the total list?
<ayrnieu>
you don't need to put min_so_far in the tuple; you pass that anyway as an argument to your recursive function. Although you don't need a tuple, either, and can just pass the two arguments.
<Smirnov>
i was talking about the rec function
<ayrnieu>
yeah, me too. Look, I've been kind of silly. If you don't understand my algorithm, that's alright. One pass to find the min and a second pass to remove the min is all you need; it even comes to my same O(N+N-k) complexity, as you don't need to walk the entire list to remove a specific value.
<Smirnov>
hmm
<Smirnov>
wouldnt my list-so-far be reversed?
<ayrnieu>
aye.
<Smirnov>
ugh..
<ayrnieu>
take my most recent advice :-) Everything else has been a very complex way of arriving at the same thing.
<Smirnov>
i think i see what u mean now
<Smirnov>
just as i got the previous algorithm..sheesh
<Smirnov>
you dont need to walk the entire list to remove a value???
<Smirnov>
how does that work ?
<ayrnieu>
Smirnov - you know that you need to remove the first occurence of a specific value, yes? You already have that value, yes? So you just test each element of the list in sequence until you match the value, yes? And then take the CDR of the previous cons and set it to the CAR of the next cons in the list. Destructive not-walking-the-entire-list removal.
<Smirnov>
CDR? CAR?
<ayrnieu>
the tl and the hd
chessguy has joined #ocaml
<Smirnov>
huh...
<Smirnov>
would it hurt to use full words?
pango_ has joined #ocaml
<ayrnieu>
take it to the List module :-)
<Smirnov>
?
<Smirnov>
ok i see what tl and hd is now
<Smirnov>
but i dont get it
<Smirnov>
as far as I see it you have to walk the entire list to remove an element, and it will get reversed to boot
<ayrnieu>
that's alright; it doesn't seem that O'Caml likes to talk about such things. Can replace the next-to-last sentence of what I said earlier with "And then destructively append the list-so-far with the list-to-go"
<Smirnov>
"destructively append" ?
<Smirnov>
so reverse the list so far and append it to the list to go?
<ayrnieu>
It's something that doesn't make sense in O'Caml; nevermind.
<Smirnov>
I have a question about This is all false, anyway, since you'll need to reverse that list at some point.
<Smirnov>
I know how to call a function like List.map, using List.map <args>
<Smirnov>
but what if its just "val func" on that page, do I call it like func <args> ?
<ayrnieu>
do you mean "val <func>", as in "val flatten : 'a list list -> 'a list" ?
<Smirnov>
yes
<Smirnov>
how would I call that one?
<ayrnieu>
List.flatten list_of_lists
<Smirnov>
oh
<Smirnov>
why doesnt it say List.flatten then
<Smirnov>
thats confusing manual notation
<ayrnieu>
because it describes the interface of List -- so the List. part is a given, and because it describes the interface by first giving the type and then describing the purpose.
<ayrnieu>
well, the signature, which includes the type.
<Smirnov>
hmm, this is what I wrote and it looks wrong
<Smirnov>
hmm, i thought my professor said ocaml doesnt have named arguments
<ayrnieu>
with labels in O'Caml, however, when labels are used, you always need to supply them. When they are not used, you cannot supply them. ListLabels and List reflect these respective choices.
<ayrnieu>
there's a closer analogue here to Smalltalk than to what Python has.
<Smirnov>
Hmm, my professor oversimplified a lot of things. strings are quite mutable
<Smirnov>
but lists are not I suppose?
llama32 has joined #ocaml
<ayrnieu>
it doesn't seem so. Perhaps I am very wrong.
<Smirnov>
Hah, there is a List.sort in the lbirary already...wee
<llama32>
would it be more difficult or much slower in ocaml to set up an array on shared memory and access it than in C?
<ayrnieu>
indeed. I'd assumed that you wanted to write your own for some reason.
<ayrnieu>
llama - it would be just as horrible, but I can't answer beyond that.
<Smirnov>
llama32: Array.make : int -> 'a -> 'a array
<Smirnov>
whoa.deja vu
zak_ has joined #ocaml
zak_ is now known as llama33
llama32 has quit [Remote closed the connection]
llama33 is now known as llama32
Smerdyakov has quit ["Leaving"]
jcreigh has joined #ocaml
f78 has quit ["Leaving"]
shawn__ has quit [Connection timed out]
jcreigh has quit ["Cuius rei demonstrationem mirabilem sane detexi. Hanc marginis exiguitas non caperet."]
_velco has joined #ocaml
Smirnov has quit [Read error: 104 (Connection reset by peer)]
shawn__ has joined #ocaml
shawn__ has quit ["This computer has gone to sleep"]
shawn__ has joined #ocaml
_jol_ has joined #ocaml
b00t has quit [Remote closed the connection]
_jol_ has quit ["leaving"]
<flux__>
ayrnieu, hm, you don't need to provide the labels always when the function uses them?
<flux__>
maybe with optional arguments, but not otherwise
<flux__>
and actually I don't know why the Labels-modules are separate..
<ayrnieu>
flux - you're saying that you don't always need to provide the labels to a Labels-module function?
* ayrnieu
tries it. Gasp! It is true!
<ayrnieu>
well then. At least you can rename the modules to be less annoying.
pango_ has quit [Excess Flood]
DRMacIver` has joined #ocaml
Snark has joined #ocaml
Carillon_ has joined #ocaml
DRMacIver has quit [Read error: 110 (Connection timed out)]
DRMacIver` is now known as DRMacIver
Carillon has quit [Read error: 110 (Connection timed out)]
_velco has quit ["I'm outta here ..."]
pango_ has joined #ocaml
Wild_Cat has joined #ocaml
d-bug has joined #ocaml
wkh has left #ocaml []
smimou has joined #ocaml
love-pingoo has joined #ocaml
_jol_ has joined #ocaml
youknow365 has joined #ocaml
<youknow365>
yo yo
<youknow365>
i need ot get serious with my im client now
<youknow365>
i have just been messing around grrrrr
<zvrba>
we don't care
<ayrnieu>
no, we do.
<youknow365>
thanks for the <3 'ing support :P
<ayrnieu>
youknow - define a specific goal (which complexity depends on your confidence) and allot it a specific amount of time (which should approach a constant). When you have the time available and some mental undisorder, start the clock the specific-amount-of-time and begin working towards the goal. When you either accomplish the goal or use the entire allotment of time, stop. Rest for a time. Evaluate what you've done
<ayrnieu>
.
<ayrnieu>
No pausing or extending the time, either. Just stop. No redefining the goal or extending or simplifying the goal, either. Just stop.
<flux__>
ayrnieu, you've found that helpful?
<youknow365>
hmmmmmm
<youknow365>
the only complaunt i have about Ocaml so far is learning it
<youknow365>
not enough tutorials and documentation
<youknow365>
alot of good docs for people that know what they are doing though
<youknow365>
i never liked the idea of recursive functions .........Loops all the way
<ayrnieu>
flux - yes. Recently I go for a constant time allotment of three hours.
meng has joined #ocaml
<youknow365>
does Ocaml have any QT libs by any chance ?
<meng>
a stupid question: how to change +. to prefix operator? many thanks
<zvrba>
put it like ( +. )
<zvrba>
# (+.) ;;
<zvrba>
- : float -> float -> float = <fun>
<meng>
thanks. i will try it. thanks
<zvrba>
you want to put spaces around () when dealing with *; otherwise it'll get interpreted as a comment
<youknow365>
some one told me ocaml had great speed and some other guy today said it was one of the slowest langs out there
<meng>
yes. i saw that in the mailing list. thanks, zvrba
<youknow365>
hmmmmm
<youknow365>
is that karmel binding complete ?
<ayrnieu>
flux - you can add my cute videogame animations about "MISSION TIME" if you like, too :-)
<ayrnieu>
youknow - ask those people.
<pango_>
youknow365: I think you'll be missing way to much if you restrict yourself to imperative features of ocaml
<youknow365>
ok
<flux__>
youknow365, the guy obviously was trolling, because there are tons of languages (well, implementations ;) ) that are slower ;)
<youknow365>
pango_: only thing i saw that is not iterative is the whole recursive functions thing
<pango_>
youknow365: then you must not have looked at a lot of code
<flux__>
ayrnieu, doesn't look too alive that project
<youknow365>
pango_: your right :P
<youknow365>
flux__: which ?
<flux__>
kamel
<ayrnieu>
flux - it doesn't, but that's why I'd ask them a question. I can still at the least take what they have as guidance.
<flux__>
judging from the size of the member list or the number of bug reports
<youknow365>
thats not a major problem
<youknow365>
i liek GTK but sometimes i prefer QT if i am using KDE
<youknow365>
i wonder if it works at all
<youknow365>
that karmel thing
_jol_ has quit ["temci lo nu citka"]
<ayrnieu>
hey, lojban.
<youknow365>
but that ocaml ncurses lib is interesting
slipstream has joined #ocaml
<youknow365>
im going to start using the mailing list
<youknow365>
seeems like there is alot of help on there
<ayrnieu>
ask questions, get answers. It probably doesn't matter where you ask the question, or who hears you. Not as much as you'd think :-)
<meng>
sorry, seems like ( symb ) will change it into infix operator, and what i want is something like +. 1. 2.;;
<ayrnieu>
yes, (+.) 1. 2.;; works just fine.
<ayrnieu>
I don't know what you mean by 'change it into an infix operator'; the operator just gets curried. It isn't special.
<meng>
ohh, thanks. im a caml noob
<meng>
i just go through the examples of the first chapter of Cousineau&Mauny. but they are written in ocaml light
slipstream-- has quit [Read error: 110 (Connection timed out)]
<ayrnieu>
That's OK. If you have questions, ask them.
<meng>
thanks. im also a lisp noob. but in lisp, operators always be prefix, so not too many confusions there ... in my opinion
<ayrnieu>
Lisp also doesn't have currying :-)
<ayrnieu>
not the automatic, natural kind that O'Caml has. It can't mix this with variable-number-of-argument functions.
<pango_>
and variable number of arguments can't be fully supported in a static typed language. It's all a matter of trade-offs ;)
<ayrnieu>
aye. A third trade-off: functions named by the number of their arguments, so that foo/1 and foo/2 have nothing necessarily to do with each other.
<pango_>
well, I suppose overloading could be supported, but type inference would then be much more complex, if decidable at all
<pango_>
type inference has already exponential worse cases
<ayrnieu>
overloading as a term doesn't really make sense, here. foo/1 and foo/2 aren't overloading 'foo'; they are completely unrelated, always distinguishable as foo/1 or foo/2 by this name or by the number of arguments clearly passed to them.
_jol_ has joined #ocaml
<ayrnieu>
this is fine and wonderful, but it can't coexist with variable-arguments or with currying.
<pango_>
the arity is a property of the signature, so I thought 'overloading' was correct. (thought your foo/1 foo/2 were mere notations, too)
<pango_>
but I guess we're globally in violent agreement nonetheless ;)
<ayrnieu>
it's more useful to think of the arity as part of the name. but: aye.
<pango_>
only in hungarian notation :)
<ayrnieu>
mainly that languages with 'overloading' of 'signatures' manage the extra details in a very different way from languages with 'functions named by arity'. However 'signature' wants to also mean this arity thing, it has a different usage. And usage is the only thing that separates 'computer' from 'processor' in this crazy world.
* ayrnieu
: reading a very nice flame, right now :-)
<pango_>
haven't used a language that names functions based on arity, so I can't tell
_jol_ has quit ["temci lo nu gunka"]
Leonidas has joined #ocaml
<meng>
let rec iter n f x = if n = 0 then x else f (iter (n - 1) f x);;
m3ga has joined #ocaml
<meng>
let fib n = fst (iter n (fun (x, y) -> (x + y, x)) (1, 0));;
<meng>
then i input fib 45;;
<meng>
the output is a negative number. why?
<meng>
thanks
m3ga has quit [Client Quit]
<pango_>
integer overflow
m3ga has joined #ocaml
<meng>
how to correct it then? thanks!
<pango_>
OCaml int type is limited to -2^31 .. 2^31 - 1
<pango_>
and OCaml doesn't check for arithmetic overflows
<pango_>
try Big_int module
<pango_>
it provides arbitrary large ints
<meng>
ohh. my lisp version works fine. i thought ocaml better than lisp in performance
<meng>
thanks anyway
<pango_>
also, your iter function is not tail recursive, you'll also have problems with that for large values of n
<pango_>
(stack overflows)
<meng>
.... thank you!
<pango_>
as long as a function is not tail recursive, function calls have to be stored somewhere...
<pango_>
at what value of n it will break, I can't tell
<meng>
thanks. you're very kind
<pango_>
much less how it'll compare to the value of n that breaks your lisp implementation of the same thing
<pango_>
np, helping people is what this channel is used for, beside flames ;)
<meng>
(fib 45) works on clisp. im not using sbcl, or other lisp implementation
<pango_>
fib n piles up n call frames at most, so I suppose you'll need large values to run into problems for any reasonable functional language implementation
<pango_>
still, if you start using arbitrary large ints, I thought it should be mentionned
<newbcoder>
honestly; I feel liike none of this is not trivially implementable based on the stuff I've seen in sicp
<ayrnieu>
newbcoder - 'an interesting type system' is not trivially implemented.
<newbcoder>
err; it's more than a directed acyclic graph?
<love-pingoo>
a DAG isn't a type system..
<newbcoder>
no but is it more general than just all the types being nodes of a DAG?
<love-pingoo>
I don't see why you ask it like that.. although I'd say yes because of polymorphism
<love-pingoo>
but listen, a static type system is about checking stuff for you at compile time, scheme doesn't have one, and caml has a very expressive one, which still doesn't require type annotations from the programmer
<ayrnieu>
I feel that I have come dangerously close to a "C is just as powerful as Perl because Perl is implemented in C! :D" kind of conversation.
shawn__ has quit ["This computer has gone to sleep"]
<love-pingoo>
trust me, that's worth trying it
Leonidas has joined #ocaml
<love-pingoo>
ayrnieu: yeah, sometimes it's hard :D
<newbcoder>
no no no; I don't mean to say all are the same since they're all turing complete
<newbcoder>
I've just been bitten by unnecessaryu features in the past; and I'd rather have a language that lts me build in the features
<newbcoder>
rather than force a bunch of predefined ones at me
<newbcoder>
what's a good source on sml vs ocaml?
<pango_>
newbcoder: Smerdyakov ;)
<newbcoder>
Smerdyakov, plese enlighten me on sml vs ocaml
<pango_>
newbcoder: you should check what "strong static typing" means. It's not just a matter of type combinaisons you can create
<newbcoder>
it's just that each var can only take on objects whose type belongs in a certain type;no?
<love-pingoo>
sml and ocaml are very similar, I don't have any real solid reason for prefering ocaml..
<ayrnieu>
newbcoder - on SML versus O'Caml, it seems that people pick one or the other wholly by syntatic preference. So if you look at both and then say "I'll use this one, because it's prettier!", you'd be in decent company. Otherwise, O'Caml has a very fine implementation, and SML has several very fine implementations, and both have books, and both have extensions, and one has a language standard.
<love-pingoo>
newbcoder: it's not "just" that, because the compiler checks it for you at compile time, which means that there's no extra check at runtime, and no type error at runtime..
<love-pingoo>
newbcoder: wait.. you should try OCaml instead of SML for the variants/labels/OO features, that's a good reason
<newbcoder>
I heard SML is mathematically rigrous, whateber that means, and ocaml is not; can anyone enlighten me on this?
<pango_>
probably not
<love-pingoo>
OCaml is a rigorous language, as far as I know
<zmdkrbou>
ocaml is as rigorous as sml, i think
<newbcoder>
how about macros; if there no need for macros in ocaml?