Re: List.flatten....

O(N) isn't bad.  The classic merge sort algorithm has O(N*Log(N))
efficiency and is considered to be one of the best sorting algorithms out
there.  O(N) is even better!  So if List.append has O(N) efficiency, isn't
that pretty good?

On Sat, Apr 2, 2016 at 2:58 PM, Kenneth Miller [email protected]
[ocaml_beginners] <[email protected]> wrote:

>
>
> The implementation of ocaml lists tells the real difference between how it
> will perform in the real world. OCaml lists are singly linked lists.
> List.append must traverse to the end of the first list and link the tail
> with the other list to complete; it is O(N) where N is the length of the
> first list. The const operator is O(1), and in nearly every function
> implementation requiring concatenation of lists you can almost ways break
> down the first list and prepend it instead of appending whole lists. Some
> cleverness might be required, but in such cases don't forget that List.rev
> can be used after all the processing is done, and it won't change the order
> of magnitude if your function is O(N) because List.rev is O(N) too.
>
>
> On Saturday, April 2, 2016 10:07 AM, "Douglas Lewit [email protected]
> [ocaml_beginners]" <[email protected]> wrote:
>
>
>
> Sure can....
> 'a -> 'a list -> a' list is for List.cons
>
> 'a list -> 'a list -> a' list is for List.append
>
> I think those 2 functions start to overlap however if you're working with
> a list of lists.  Well "overlap" could be a poor choice of words, but what
> if 'a refers to a list and 'a list -> refers to a list of lists, so then
> you would have something like:
>
> [1; 2; 3; 4] :: [[5; 6; 7; 8]] ;;
>
> The result is a list of lists or nested lists.
>
> A professor of mine is studying Haskell.  I asked him if he liked it, to
> which he replied.... "It's very LISTY".  And I think LISP is really an
> acronym for LISt Processing.  It seems that this is a hallmark of most ( or
> all? ) functional programming languages.  A big emphasis on lists and list
> manipulations.  Of course how do you define a list?  In some languages the
> words "array" and "list" are interchangeable.  ( I think Python for example
> does have arrays, but in general in Python arrays and lists are
> interchangeable. )  I read somewhere that Ocaml lists have more in common
> with Java linked lists than Java arrays.
>
> Okay.... I'm rambling!  I better shut up!  I hope everyone on the list has
> a great weekend.
>
> Best,
>
> Douglas.
>
>
> On Sat, Apr 2, 2016 at 5:33 AM, 'Mr. Herr' [email protected]
> [ocaml_beginners] <[email protected]> wrote:
>
>
>
>
> On 02.04.2016 07:32, Douglas Lewit [email protected] [ocaml_beginners]
> wrote:
>
>
>
> I think I read somewhere that the cons operator :: is more efficient than
> the append operator @, so whenever possible it's better to use cons rather
> than append.
>
> # List.cons ;;  (* this is :: *)
>
> - : 'a -> 'a list -> 'a list = <fun>
>
> # List.append ;;  (* this is @ *)
>
> - : 'a list -> 'a list -> 'a list = <fun>
>
> #
>
>
> there is a tiny little difference, can you find it?
>
> /Str.
>
>
>
>
> 
>