<moea>
it works, but i was wondering if someone could critique the style, or help me simplify it
<moea>
its very scheme-like
Saulzar has joined #ocaml
<ski>
moea : i believe recursivel calling like this 'digits @ [m]' is bad (expensive to append thinks to growing lists)
<moea>
ski: is there some way to remove the explicit accumulation entirely?
<moea>
in python, for example, i would yield each digit
<ski>
try consing m in front of list, and explicitely reverse the resulting list in the initial call i.e. in this call 'in loop n [];;'
<moea>
how do you cons in ocaml?
<moea>
:: ?
<ski>
yes
<moea>
ski: and list reversal?
<ski>
rev
<moea>
thanks for your help
<ski>
i.e. List.rev (rev is in module List)
<Amorphous>
ski: i heard 'foo @ [bar]' is constant time. is that incorrect? or is it expensive because of the recursive call can not be optimized enough?
<ski>
generally, with linked-lists, appending stuff takes time proportional to length of first list, in this case the list grows on recursion, so the total time is proportional to square of length of first list (which is bad, because we can do better)
<ski>
and, if not compiler manages to rewrite the code into more efficient code (which i don't know if it manages to do in this case .. not so familiar with optimizations in ocaml), 'foo @ [bar]' is *not* constant time
<moea>
is the code is pasted pretty much idiomatic?
<ski>
i believe so
<ski>
though seems a bit much indentation ..
<ski>
(if we had an unfold function somewhere, we could write it shorter .. can't remember if there is such defined .. of course one can define one such oneself)
<moea>
ski: thanks
* ski
'd prolly use an indentation of 2-4 spaces ..
<ski>
and the indentation for the body of the innermost let looks weird (to me)
<ski>
i'd just indent it the same as the let (possibly putting 'in' at the next line, and indenting the body after that, i.e. 3 spaces)
<ski>
moea : yw
fab__ has joined #ocaml
Boojum has joined #ocaml
Snark has quit [Nick collision from services.]
Boojum is now known as Snark
_fab has quit [Read error: 113 (No route to host)]
Saulzar has quit ["Leaving"]
Gueben has joined #ocaml
fab__ has quit []
moea has quit [Read error: 104 (Connection reset by peer)]
ramkrsna has joined #ocaml
GuebN has joined #ocaml
Gueben has quit [Nick collision from services.]
GuebN is now known as Gueben
Tom_n3m has joined #ocaml
rossberg has quit ["Leaving"]
moea has joined #ocaml
<moea>
ocaml is my friend
<ski>
wb
<moea>
thanks
<petter_>
hmm, anybody know if the G'Caml stuff will ever be in O'Caml?
<petter_>
im reading the gcaml README, it's very cool...
<ulfdoz>
re
vezenchio has joined #ocaml
Snark has quit [Read error: 110 (Connection timed out)]
Snark has joined #ocaml
<Tom_n3m>
gcaml is cool, yeah...
<Tom_n3m>
I wonder, does it check all the types at compile time... or dynamically, at runtime?
<Tom_n3m>
any1 knows?
<mflux>
of course compile time
<mflux>
although didn't it support some dynamic types too? for those runtime..
<mflux>
while the types are checked compile time, I believe the code executed is very dynamic
<mflux>
well, sortof
<petter_>
well, I guess you could simulate that kind of flat function with variants
<petter_>
but thats kind of adding type information yourself
<petter_>
so at runtime the flat function has to know if its argument is a list list or a list...
<mflux>
and it doesn't need to know
<mflux>
List.concat [[[1]]] and List.concat [[1]] work too
<mflux>
and List.concat doesn't really know what kind of list it is concatenating
mikeX has joined #ocaml
<petter_>
hmm, but the way I understood it was: "List.concat [[[1]]]" will return "[[1]]", but the flat function would return "[1]"
<Tom_n3m>
indeed, but in this case, its easy. on [[[1]]], the flat : int list list list -> whateveris called, and in case of [[1]], flat : int list list -> whatever is applied
<Tom_n3m>
the concept of dyn type is (on my oppinion) extremely useful. One could query runtime types, just like it's possible in interpreted environments (.NET framework, java).
<petter_>
yes, the dyn type is very interesting
<mflux>
petter_, yes, because it has the recursion termination for returning the list itself..
<mflux>
but ocaml cannot case on compile time type
<Tom_n3m>
But, based on my insight into GCaml's source, the implementation isn't very efficient
mikeX has quit ["Leaving"]
<Tom_n3m>
for every value is blocked, most (all except integers) even two times
<petter_>
hmm, if I call "flat [[[1]]]" i g'caml, how does it decide wich of the cases to run? that information had to be there at runtime
vincenz has quit [Read error: 110 (Connection timed out)]
<petter_>
of course, the way I wrote it, the information is there at compile-time that this is a int list list list, but if it's a list built dynamically where you don't know the depth?
<mflux>
yes, but it can still be type-checked compile time
<petter_>
oh, I think I see my error
<petter_>
for nested lists to have non-uniform depth, you'd have to use dyn, right?
<mflux>
I think so
<petter_>
so just as you know the type of the list in "[[[1]]]", if you call "fun_returning_nested_list", you know the type of that function of course
<Tom_n3m>
hm... you can't really have lists of unknown depth.
<Tom_n3m>
every list in a type declaration means one depth.
<petter_>
yes
<Tom_n3m>
int list list list list list , thus, has 5 depths
<petter_>
you'd have to use a variant type
<petter_>
in o'caml, in g'caml i guess you'd use dyn
<Tom_n3m>
I believe (or, actually, hope) not. The dyn type is much less efficient that statically (at compile time) determined types
<petter_>
like "type 'a ulist = Atom of 'a | List of 'a ulist"
<petter_>
so using variants is sort of adding your own dynamic typing, so "dyn" shouldn't have to be less efficient
<mflux>
yeah, but it cannot be checked compile time
<petter_>
which?
joeytwiddle has quit ["Leaving"]
<mflux>
dyn-stuff
<petter_>
yes, now that i look at it
<petter_>
dyn allows ANY type
<petter_>
does anyone know of other languages with type systems similiar to g'caml?
<mflux>
I haven't heard, but have you taken a look at Haskell?
<mflux>
it has type classes
<petter_>
I've done some haskell, in the "functional programming" course at my university
<petter_>
that was a while ago, and I didn't understand as much about type systems back then
<petter_>
not that I do now, I just find it much more interesting now
<petter_>
hmm, so in haskell, the type of "(==)" is "(Eq a) => a -> a -> Bool", which means that a has to be of the type class Eq
<Tom_n3m>
That's then similar to java, I guess. The class of an object is determined, then the desired function, one specific to thic class, is called
vezenchio has quit [Read error: 104 (Connection reset by peer)]
<ski>
it's a bit similar to java interfaces, but just a bit (and also more general, in some ways)
vezenchio has joined #ocaml
Tom_n3m has quit ["Real programmers use: COPY CON PROGRAM.EXE"]
Tom_n3m has joined #ocaml
ramkrsna has quit [Read error: 110 (Connection timed out)]
monochrom has joined #ocaml
<Amorphous>
ski: last time i checked, appending to the end of an linked list was O(1). did i miss something?
Skal has joined #ocaml
kothog has joined #ocaml
moea has quit [Read error: 104 (Connection reset by peer)]
<ski>
Amorphous
<ski>
val append : 'a list -> 'a list -> 'a list
<ski>
Catenate two lists. Same function as the infix operator @. Not tail-recursive (length of the first argument). The @ operator is not tail-recursive either.
<ski>
Some functions are flagged as not tail-recursive. A tail-recursive function uses constant stack space, while a non-tail-recursive function uses stack space proportional to the length of its list argument, which can be a problem with very long lists.
<Amorphous>
ski: so it's about tail-recursion and not complexity... thx
<ski>
tail-recursion is about complexity
<ski>
space complexity
<ski>
(well, that's one of the things it's about, anyway)
<Amorphous>
yea i though about time complexity
<mflux>
amorphous, adding to the end of a list for which you don't have the tail pointer is O(n)
<ski>
time-complexity is proportional to size of first list (because it must recurse through and copy that)
<Amorphous>
mflux: i assumed that
<mflux>
I assumed you talked about ocaml lists ;)
<ski>
destructive/mutable double-linked, (or link to tail) can have constant append (and prepend)
Snark has quit [Read error: 60 (Operation timed out)]
<ski>
also ((((... @ ...) @ ...) @ ...) @ ...) @ ... is bad
<Amorphous>
mflux: ah so lists in ocaml don't store a tail pointer, good to know.
<ski>
so, when one sees the pattern let foo ... = ... ((foo ...) @ ...) ...;; one knows this is proll ybad complexity
<mflux>
amorphous, lists can be thought as: type 'a list = Empty | List of ('a * 'a list)
<ski>
lists are more or less just type 'a list = [] | op :: of 'a * 'a list;; i.e. just another variant type
* ski
smiles
<mflux>
damn, it would've been pretty if I had used the same notation ;)
<Amorphous>
ski: why can't immutabel linked lists with link to tail have constant append? (immutable means only "write protected", right?)
<ski>
we need to copy first list
<ski>
(because it can be shared)
<ski>
in a lang with a uniqueness/linear typesystem like Clean (or Mercury), where the system can guarrantee things to be unique (i.e. sole reference to a value), there one can possibly have constant append, i think
<mflux>
amorphous, to append an element you would need to modify the last element to point to the newly appended element, and that's a mutation
<Amorphous>
mflux: oh so objects are appended and not only a reference to them?
<mflux>
amorphous, even adding a reference to them would modify the original list
<Amorphous>
oh ok i missed that.
<mflux>
amorphous, because after appending the element the appended element would be reachable from the head of the list
<mflux>
which may be shared, which was ski's point
<mflux>
so all you can do is add new refrences to the list, and the new references may be interpreted as prepending elements to the list
<mflux>
what some (well, atleast my) ocaml algorithms do is that they build the list in reverse, and then, in the final step, reverse the list to produce the final answer
<mflux>
this is reasonably efficient
<ski>
one can also rewrite to accumulator style
<ski>
in some cases, at least
<mflux>
I thought that was accumulator style?-)
<ski>
i.e. build the list from bottom-up
<ski>
think of a simple tree-flatten
<ski>
let rec treeFlatten Nil = [] | treeFlatten (Node (left,x,right)) = treeFlatten left @ (x :: treeFlatten right);;
<Amorphous>
now i understand :) thx ski, mflux
<ski>
we can do instead let treeFlatten tree = let rec helper Nil acc = acc | helper (Node (left,x,right)) acc = treeFlatten left (x :: treeFlatten right acc) in helper tree [];;
<ski>
see, no reverse
<mflux>
well, happily trees are something with which the order can be easily switched during the algorithm
<ski>
switched ?
<ski>
that generates list in same order
<mflux>
I had never given a thought to using accumulators with trees, but that does come up nicely
<mflux>
but let's say we want a function that reads the contents of a file and returns the lines in a list, in the same order, it is more difficult to avoid reversing there?
<mflux>
(while using tail-recursion)
<shining>
I don't know how to run programs that display something
<mflux>
sometimes it could be convenient to have types for lists and reversed lists ;)
<shining>
it displays what I want for less than one second, then it ends
<ski>
mflux : yes, it only works in some cases
<shining>
I've to copy the program in the toplevel system each time
ejt has joined #ocaml
<petter_>
shining "#use "file.ml";;"
<shining>
hmm yes, I just saw that again in the doc
<shining>
it helps
<shining>
otherwise, I think there was a way to let the program wait for an user input
<zvrba>
what's wrong with input_line ?
<zvrba>
input_line stdin waits for input
<zvrba>
or I don't understand what you're trying to do
<shining>
I compiled my program like that : ocamlc graphics.cma prog.ml
<shining>
then I run it with ./a.out
<shining>
and I don't have the time to see what it displays
<shining>
because as soon as it's displayed, the program ends and close the graphic
<shining>
but I can use the toplevel
monochrom has quit ["good morning, sweet dream"]
<mflux>
put Unix.sleep 42 to the end of your program?
<mflux>
or use some other mechanism provided by Graphics
<petter_>
maybe "ignore Graphics.read_key"
<Tom_n3m>
even better:
<Tom_n3m>
make a infinite loop around Graphics.read_key, and every time, check for dome specific key (as "x", exit, or "q" quit).
<Tom_n3m>
When it is pressed, end the program
<shining>
Tom_n3m: thanks, it works fine
<Tom_n3m>
np
__DL__ has quit [Remote closed the connection]
Esine has quit [Read error: 110 (Connection timed out)]
Tom_n3m has quit ["Killed (ChanServ (You've been online too long))"]
shining has quit [Read error: 110 (Connection timed out)]
zigong has joined #ocaml
ski has quit ["Zzz"]
zigong has quit ["using sirc version 2.211+KSIRC/1.3.11"]
mikeX has joined #ocaml
ejt has quit ["leaving"]
mikeX has quit ["Leaving"]
znutar has joined #ocaml
threeve has joined #ocaml
ulfdoz_ has joined #ocaml
ulfdoz has quit [Read error: 110 (Connection timed out)]