Appending to a list?

[Brad O'Hearne]

I was looking around at various list functions, and noticed a rather conspicuous omission in the Elixir documentation: 

-----

Updating a list is fast as long as we are prepending elements:

iex> [0 | list] [0, 1, 2, 3]

-----

...but there is no mention of appending elements. I did some searches on this list and found some references to appending vs. prepending (which actually clarified that both scenarios given -- [ element | list ] and [ list | element] were prepending, neither were appending), but nothing that actually answered the questions: 

1. What is the conventional way to append to a list? I understand the performance implications of traversing a list -- however, this doesn't eliminate the common need to append to a list, which can be inflicted by API function parameter data types (e.g. if an API function wants a list parameter that you have to dynamically build for some reason, and if ordering makes a difference, building a list in sequence is important). 
2. Why is there no list append operator (assuming there isn't one -- without creating another list out of the element and using the ++ operator)? If prepending was deemed a need (it is), why not appending (likely the more common need)? 

Guidance appreciated....whatever the answers, the doc probably ought to be updated...a mention of prepending begs the question of appending. 

Thanks, 

Brad

[Elliot Crosby-McCullough]

It's not made clear in the elixir docs but building the list backwards and reversing it is the usual way.  It's more clearly laid out in erlang's docs: http://erlang.org/doc/efficiency_guide/listHandling.html

--
You received this message because you are subscribed to the Google Groups "elixir-lang-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-ta...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-talk/8b4cb74d-06ff-4840-9698-9091c3c672c5%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Dave Aronson]

On Thu, Jun 16, 2016 at 11:23 AM, Brad O'Hearne <brad.o...@gmail.com> wrote:

> I was looking around at various list functions, and noticed a rather
> conspicuous omission in the Elixir documentation:
>
> -----
>
> Updating a list is fast as long as we are prepending elements:
>
> iex> [0 | list] [0, 1, 2, 3]
>
> -----
>
> ...but there is no mention of appending elements.

I'm just learning Elixir but I'm getting the definite impression that
prepending is much more "Elixirish" than appending....

--
Dave Aronson, consulting software developer of Codosaur.us,
PullRequestRoulette.com, Blog.Codosaur.us, and Dare2XL.com.

[Brad O'Hearne]

On Thursday, June 16, 2016 at 8:40:23 AM UTC-7, Elliot Crosby-McCullough wrote:

It's not made clear in the elixir docs but building the list backwards and reversing it is the usual way.  It's more clearly laid out in erlang's docs: http://erlang.org/doc/efficiency_guide/listHandling.html

Elliot, 

Thanks for the reply -- that definitely gives me a better understanding behind the way it ought to be implemented. However, the erlang doc even says: 

"Looking at how lists:append/1 or ++ would be implemented in plain Erlang..."

Why isn't there a Lists.append/1 or an operator in Elixir? Is everyone writing their own implementation every time they need to append to a list? I mean "++" isn't painful, of course, but having to convert elements to a list prior to concatenation semantically expresses a slightly different relationship, which can lend itself to less clarity in a heavily-nested, recursive processing situation. I'm just curious, it seemed an odd omission to leave out an append operation (or any reference to how to do so) when the language acknowledges list element deletion, replacing, prepending, concatenation, and subtraction. 

B

[Onorio Catenacci]

Because of the O(n) performance of appending to a list, it's almost always suggested to prepend and reverse the list at the end. And that's not just Elixir--that's pretty much every functional language from Lisp on.  At least that's the advice I've seen in F#, Scala, Clojure, Kotlin and a few other FP languages I played with a bit.

In case anyone is unclear O(n) means performance varies directly by the size of the list.  That is, appending a new element to a list of 2 elements would be six times faster than appending an element to a list of 12.  The list of 12 would be six times slower (all else being equal).  Prepending is O(1) which means no matter how many elements are present in the list, the performance is constant.  Prepending a new element to a list of 2 elements or 12 elements takes exactly the same amount of time (all else being equal).  

That said I believe ++ (http://elixir-lang.org/docs/stable/elixir/Kernel.html#++/2)  is the recommended way to append to a list if it's needed.  I can see your point about this not being explicitly spelled out in the docs though.

[Eric Meadows-Jönsson]

On Thu, Jun 16, 2016 at 5:56 PM, Brad O'Hearne <brad.o...@gmail.com> wrote:

Thanks for the reply -- that definitely gives me a better understanding behind the way it ought to be implemented. However, the erlang doc even says: 

"Looking at how lists:append/1 or ++ would be implemented in plain Erlang..."

Why isn't there a Lists.append/1 or an operator in Elixir? Is everyone writing their own implementation every time they need to append to a list? I mean "++" isn't painful, of course, but having to convert elements to a list prior to concatenation semantically expresses a slightly different relationship, which can lend itself to less clarity in a heavily-nested, recursive processing situation. I'm just curious, it seemed an odd omission to leave out an append operation (or any reference to how to do so) when the language acknowledges list element deletion, replacing, prepending, concatenation, and subtraction. 

There is no way of appending an element to a list in Erlang either. In Elixir and Erlang we use `list ++ [elem]` to append elements. Is that really so much worse than `list ++ elem`? It is uncommon to append an element to a list since, as others have said, it is inefficient. In the majority of cases you would design your data structures and APIs so that you only prepend to lists and then at some point reverse the list.

--

Eric Meadows-Jönsson

[Brad O'Hearne]

On Thursday, June 16, 2016 at 8:44:16 AM UTC-7, Dave Aronson wrote:

I'm just learning Elixir but I'm getting the definite impression that
prepending is much more "Elixirish" than appending....

Dave -- Thanks for the reply. I get that a language may suggest various implementation approaches for things. But "prepending" and "appending" aren't really -ishes of languages -- they are algorithmic needs that are language agnostic -- no matter what language used, it is a logical need that has to be accomplished. 

On Thursday, June 16, 2016 at 9:03:56 AM UTC-7, Onorio Catenacci wrote:

That said I believe ++ (http://elixir-lang.org/docs/stable/elixir/Kernel.html#++/2)  is the recommended way to append to a list if it's needed.

Onorio -- Thanks for the reply, and your clarification, which helps my understanding. I thought the "++" might be the goto, and that's how I ended up implementing. But for several reasons: API symmetry, language clarity, and clarity in developer code, I'd recommend that there be a List.append/1 added, and it would be great if there were an operator available too. 

There is a difference between an approach to implementation (under the hood) and logical need (typically exposed via the API), and they aren't exclusive -- both can (and usually do) gracefully coexist. Language philosophy and performance implications don't erase logical algorithmic needs. In this case, what is efficient (prepending) in implementation doesn't need to erase the logical need (appending) -- A List.append/1 can implement however necessary for efficiency under the hood....but the "append" is still the logical end the user is looking for. 

My 1 cent.... (I'm on a budget, trying to save)

B

 

[Brad O'Hearne]

On Thursday, June 16, 2016 at 9:18:27 AM UTC-7, Eric Meadows-Jönsson wrote:

There is no way of appending an element to a list in Erlang either. In Elixir and Erlang we use `list ++ [elem]` to append elements. Is that really so much worse than `list ++ elem`? It is uncommon to append an element to a list since, as others have said, it is inefficient. In the majority of cases you would design your data structures and APIs so that you only prepend to lists and then at some point reverse the list.

Nope...it isn't bad (in this case). In fact, that's how I implemented (and have done so all over the place in various recursive function calls prior). But it also isn't technically what I'm trying to accomplish, and I've had the same thought every time I've done it, so I decided to go did a little bit to find out the reason why, and then ask the question this time. The thing that got me to thinking about it was populating the "children" list of workers in the startup of a Phoenix web app. I needed to conditionally add elements to that list in sequence. I accomplished this in about 30 seconds, so this isn't an issue with being unable to accomplish the task (though I rather would have done it with a single operator or expression that illustrated exactly what I was intending). 

I both create and consume a lot of APIs, and there can be a subtle philosophy that creeps into API design that what is efficient to implement is synonymous with what logical needs are --- they aren't synonymous. Users will always have the need to prepend, append, insert, replace, delete, clear, copy, etc. elements of a list. Those are logical needs of a list, a fundamental data structure, same as queues, stacks, etc. have their own needs. Take a stack for instance -- that is a fundamental data structure with canonical operations. It wouldn't be a good idea to eliminate the "push" operation because (hypothetically) language X made concatenating the entire contents of the existing stack to the element to be pushed a more efficient operation. Sure, the underlying implementation can take that approach if it is most efficient, but that should be a black-box implementation detail, not a requirement placed on the user of a stack -- the stack data structure should expose "push".

The general idea is maintaining consistent logical metaphors and data structures regardless of implementation approach. Just a suggestion. At the very least I think it improves clarity of the language and resulting code. 

Cheers, 

Brad

[Greg Vaughn]

Typically, you should be using Enum.map to preserve the conceptual ordering (which behind the scenes does a prepend, then reverse at the end) or some other higher order function, or a for comprehension. There are much better options if you abstract your operation a bit.

This is a pretty fundamental approach for immutable data structures. I'm against an api and an operator for appending to lists. Doing things in a bad way should have a syntactical disadvantage IMHO. oldlist ++ [newelement] is good enough when needed.

-Greg Vaughn

> --
> You received this message because you are subscribed to the Google Groups "elixir-lang-talk" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-ta...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-talk/49ab82ff-afb3-4cb8-9b44-951c1f91ba17%40googlegroups.com.

[Greg Vaughn]

OK, Brad, based upon this email, perhaps the better advice is to make sure that you're using the correct data structure for your problem. In functional programming a "list" is a specific data structure, much more constrained than the vernacular use of the word "list". It inherently has this O(n) behavior for appending.

Perhaps (though I am skeptical) what your problem really needs is an array. Erlang offers one (http://erlang.org/doc/man/array.html)

-Greg Vaughn

> --
> You received this message because you are subscribed to the Google Groups "elixir-lang-talk" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-ta...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-talk/e99166d2-ebc1-4a4b-93f0-c0075a15f576%40googlegroups.com.

[Brad O'Hearne]

On Thursday, June 16, 2016 at 9:48:05 AM UTC-7, Greg Vaughn wrote:

Typically, you should be using Enum.map to preserve the conceptual ordering (which behind the scenes does a prepend, then reverse at the end) or some other higher order function, or a for comprehension. There are much better options if you abstract your operation a bit.
This is a pretty fundamental approach for immutable data structures. I'm against an api and an operator for appending to lists. Doing things in a bad way should have a syntactical disadvantage IMHO. oldlist ++ [newelement] is good enough when needed.

Fair enough for the Enum.map approach. But if Elixir is going to include a List module (which acknowledges that data structure), why are certain logical operations deemed good, and others bad? How is "appending" considered "doing things in a bad way"? How an append is "done" is a function of implementation, not in any way affected by exposing an append function on List. This is kind of what I was referring to in a previous post about separating language-agnostic logical / algorithmic needs vs. its implementation. What you are saying essentially would classify the "enqueue" operation of a queue data structure as "doing things in a bad way" because Elixir's implementation would be prepend / reverse. The point I'm making is that having an implementation of prepend / reverse is great, but it doesn't negate the need for an "enqueue" operation to be exposed on a queue data structure. 

B 

[Redvers Davies]

Enough people have commented already about how it typically isn't done.

If however you do need a "list" you can append and prepend to you can reach for the erlang :queue module.

Thanks,

Red

[Brad O'Hearne]

On Thursday, June 16, 2016 at 9:59:04 AM UTC-7, Greg Vaughn wrote:

OK, Brad, based upon this email, perhaps the better advice is to make sure that you're using the correct data structure for your problem. In functional programming a "list" is a specific data structure, much more constrained than the vernacular use of the word "list". It inherently has this O(n) behavior for appending.

Understood....but I'm getting at the more general point, not the specific data structure so much. If the answer is "List data structures logically don't have append operations", then that would be a good answer (if true). But an answer of "there is no list append operation because in order to implement that we have to do something different to accomplish that" is not a good answer, as that essentially makes implementation dictate API, not the other way around. Look through the Elixir doc, you'll find that all sorts of operations are exposed on List, and the need to append is even acknowledged in list concatenation, but because of implementation details, there's this one obvious hole in operations on List -- append element.  That was my point. 

At any rate, point made. I thank everyone for their input, and guidance. 

Brad

[Dave Aronson]

On Thu, Jun 16, 2016 at 12:22 PM, Brad O'Hearne <brad.o...@gmail.com> wrote:

> On Thursday, June 16, 2016 at 8:44:16 AM UTC-7, Dave Aronson wrote:
>>
>> I'm just learning Elixir but I'm getting the definite impression that
>> prepending is much more "Elixirish" than appending....
>
> Dave -- Thanks for the reply. I get that a language may suggest various
> implementation approaches for things. But "prepending" and "appending"
> aren't really -ishes of languages -- they are algorithmic needs that are
> language agnostic -- no matter what language used, it is a logical need that
> has to be accomplished.

I think we're talking past each other. Let me explain what I mean.

In certain languages, various things are commonly done in certain
specific ways, that may differ from other languages. For instance, in
Ruby, "shoveling" (<<) or "pushing" things onto the end of an Array
(closest it has built-in to a List) is certainly common, and is
probably (I haven't looked, just guessing) more performant than
"unshifting" them onto the front. Likewise, in C a list is most
likely to be linked by pointers, and to have a tail-pointer, making
insertion at the end O(1), so appending is no big deal. Similarly,
many implementations have an explicit head-pointer (rather than
"being" a pointer to the first element), so insertion at the front is
also O(1). In such cases whether you ap-pend or pre-pend tends to
de-pend on exactly what you're trying to do, i.e., whether you're
treating it as a logical queue, stack, or whatever. But in Erlang,
and therefore in Elixir, the way Lists work under the hood (if I'm
interpreting the comments rightly) seems to make appending inefficient
(O(n)), and therefore generally avoided. It's that tendency to avoid
appending in favor of prepending, revising an algorithm if needed,
that I'm seeing as Elixir-ish, i.e., a common feature of Elixir code.

On the other claw, I've only seen maybe a few thousand lines of
Elixir, and maybe a few dozen of Erlang, so I may be wrong about the
tendencies....

[Onorio Catenacci]

If I felt the need to add a "List.append" function to an API, it's trivial to implement:

defmodule ListExtension do

  def append(list, item) do

    r = Enum.reverse(list)

    n = [item | r]

    Enum.reverse(n)

  end

end

l = [1,2,3]

#=> l = [1,2,3]

l2 = ListExtension.append(l,4)

#=> l2 = [1,2,3,4]

Every language designer and maintainer makes certain choices about what to include and what not to include.  I wouldn't presume to guess why the core committers didn't feel a need for a List.append but since it's trivial to implement for yourself if you really need it, just implement your own.

--

Onorio

--
You received this message because you are subscribed to a topic in the Google Groups "elixir-lang-talk" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/elixir-lang-talk/BR7wPpG9tzw/unsubscribe.
To unsubscribe from this group and all its topics, send an email to elixir-lang-ta...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-talk/ab9767e6-1998-439f-af6b-1f72b237ad06%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

Onorio Catenacci
 
http://onor.io

http://www.google.com/+OnorioCatenacci

[José Valim]

> Fair enough for the Enum.map approach. But if Elixir is going to include a List module (which acknowledges that data structure), why are certain logical operations deemed good, and others bad? How is "appending" considered "doing things in a bad way"? How an append is "done" is a function of implementation, not in any way affected by exposing an append function on List.

The reason there isn't such function in List is because we already have ++ in Kernel. Some could argue that List.append would be useful for developers that are not familiar with ++ but I would rather make sure we teach developers about ++ because it is more useful than List.append (as ++ is allowed in patterns).

It is the same reason why we won't have Integer.add/2. We had similar complaints in the past about developers not finding the map functions in the List module because they are in Enum. I will make sure to improve the docs for List once again to mention appending.

If we didn't have ++, List.append would be very useful because it would be the place we would add warnings about the costs of using it, specially in a loop.

> The thing that got me to thinking about it was populating the "children" list of workers in the startup of a Phoenix web app.

I would just like to use this example to mention that solving this with an append operation is a very imperative way of thinking about the problem. I know that because I wrote this imperative code in Elixir dozens of times. Instead of writing something like:

    children =

      if add_conditional_child?(opts) do

        children ++ [new_child] # Or List.append

      else

        children

      end

You should either use an empty list for representing absence and concatenate/append all the way:

default_children() ++ conditional_children(opts) ++ other_conditional_children(opts)

Or build a list with tuples and filter it later on:

children = [

  {:ok, child1},

  {:ok, child2},

  conditional_child(opts), # {:ok, child} | :error

  other_conditional_child(opts), # {:ok, child} | :error

]

for {:ok, child} <- children, do: child

For this particular case, List.append wouldn't help you.

[José Valim]

It should be:

defmodule ListExtension do

  def append(list, item) do

    list ++ [item]

  end

end

José Valim

www.plataformatec.com.br

Skype: jv.ptec

Founder and Director of R&D

--
You received this message because you are subscribed to the Google Groups "elixir-lang-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-ta...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-talk/CAP%3DvNq-o1z9R5P35oGNb-F5XX6qxs1gmc_zDkh5p%2BuLdkKY13w%40mail.gmail.com.

[Onorio Catenacci]

Yeah I thought of that after I posted it.  :)  The reverse list, prepend, reverse again approach is deep in my fingertips. Thanks José :)

--

Onorio

To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-talk/CAGnRm4Ksb-xEG7yCoDsjYctz0gHSMDWnA49Ag%2BAm2R9-8QkOvQ%40mail.gmail.com.

For more options, visit https://groups.google.com/d/optout.

[Brad O'Hearne]

On Thursday, June 16, 2016 at 10:23:04 AM UTC-7, José Valim wrote:

The reason there isn't such function in List is because we already have ++ in Kernel. Some could argue that List.append would be useful for developers that are not familiar with ++ but I would rather make sure we teach developers about ++ because it is more useful than List.append (as ++ is allowed in patterns).

Thanks for this reply, Jose. This rationale behind the design is exactly what I was looking to understand, so this is greatly appreciated.

 

> The thing that got me to thinking about it was populating the "children" list of workers in the startup of a Phoenix web app.

I would just like to use this example to mention that solving this with an append operation is a very imperative way of thinking about the problem.

Agreed when thinking about underlying implementation. But the higher-level logical end of "we need this element X at the end of element Y" (or append) is the same, no matter what the most efficient underlying implementation may be. The primary point I was trying to make was that just because there exists a particular way to accomplish something, it doesn't eliminate the value of the abstraction (perhaps not in all cases, but in some, and most definitely for clarity which will help newcomers). 

A humorous illustration of this: I can take the lid off of the water tank reservoir and pull the plunger with my hand to flush my toilet -- it is a perfectly valid approach, and figuratively as "close to the metal" as it gets. But because that way exists, it doesn't eliminate the need, convenience, or desire for the abstraction of the flush lever outside the water tank.  

Can we dub the prepend vs. append question "The Yoda Issue"? I've been chuckling to myself about how this discussion has similarities with how Yoda structures phrases. I have been imagining him posting a reply to this thread which says: 

"To place at end, add list to front, we must." 

At any rate, thanks for the replies Jose, (and everyone), that really helps. 

Brad

[Dave Aronson]

On Thu, Jun 16, 2016 at 2:02 PM, Brad O'Hearne <brad.o...@gmail.com> wrote:

> Can we dub the prepend vs. append question "The Yoda Issue"? I've been
> chuckling to myself about how this discussion has similarities with how Yoda
> structures phrases. I have been imagining him posting a reply to this thread
> which says:
> "To place at end, add list to front, we must."

That reminds me more of https://www.youtube.com/watch?v=6LR6eS2NWf4

;-)

[Brad O'Hearne]

On Thursday, June 16, 2016 at 11:10:23 AM UTC-7, Dave Aronson wrote:

That reminds me more of https://www.youtube.com/watch?v=6LR6eS2NWf4

Dave -- ROTFL! Well played! That reminded me of this (perhaps dating myself a bit) the famous "Bizarro Jerry" episode from Seinfeld: 

https://www.youtube.com/watch?v=0LPIc5JIFwk

Cheers! 

B

[Peter Hamilton]

I would also argue that a singly-linked list of immutable nodes does not have a logical append operation. Perhaps we should rename the List module to ImmutableSinglyLinkedList (I jest). It does however have a logical pure concatenate operation. So while a generic List data structure should provide an append operation, we don't actually have a generic List. We only have an ImmutableSinglyLinkedList, and therefore should limit our abstraction.

I do wonder if Enumerable could capture the more generic concept of adding and removing from an enumerable, though append and prepend imply ordering which Enumerable does not require.

In the end, I agree with the sentiment that logically we shouldn't think about appending to (immutablesinglylinked)lists. Concatenating better captures the operation and I think this difference should influence how we frame our problems.

--
You received this message because you are subscribed to the Google Groups "elixir-lang-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-ta...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-talk/CAHxKQijhhSWdU5r3rGOgwasThzRJO8uq0XxfdvwP6G_7x-6wMg%40mail.gmail.com.

[Brad O'Hearne]

On Thursday, June 16, 2016 at 11:19:41 AM UTC-7, Peter Hamilton wrote:

I would also argue that a singly-linked list of immutable nodes does not have a logical append operation. Perhaps we should rename the List module to ImmutableSinglyLinkedList (I jest). It does however have a logical pure concatenate operation. So while a generic List data structure should provide an append operation, we don't actually have a generic List. We only have an ImmutableSinglyLinkedList, and therefore should limit our abstraction.

If truly immutable, then maybe true for the append operation, as long as that same principle applies to other List operations. But calling a List immutable as rationale for disqualifying append, and then green-lighting prepend, delete, delete_at, flatten, insert_at, keydelete, keyreplace, keystore, replace_at, and update_at, all which presently exist, appears to be a pretty contradictory situation. 

B   

[Peter Hamilton]

Yeah. That's a good point, I agree.

So prepend is really the only exception, because you can prepend to a singly-linked list of immutable nodes.

I withdraw my argument. Thanks!

--

You received this message because you are subscribed to the Google Groups "elixir-lang-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-ta...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-talk/c34c393e-04cd-4a53-8058-101ad39c5b8b%40googlegroups.com.

[Rich Morin]

Folks in any modern language community will know a variety of names for
a given bit of functionality. For this reason, Matz has created aliases
for various methods in Ruby. For example, Enumerable.inject() comes from
Smalltalk. In Ruby, it can also be called as "reduce" (but NOT "foldl";
too bad for the Lisp folks :-).

Although I understand the reasoning behind this, it has never seemed all
that clean as a solution. If I am looking for "foldl", it may take me a
while to figure out that I need to search for "inject" or "reduce". The
use of aliases also increases the surface area of the language, making
it harder to learn and remember.

However, it occurs to me that Elixir might be able to handle this sort
of issue, simply by adding some documentation. Elixir has reduce, but
not foldl or inject. Why not allow these synonyms to be recognized by
the documentation tools, providing redirects to the "official" name?

I could imagine, for example, adding an attribute such as @synonym.
In the Enumerable protocol, the def for reduce could be preceded by:

@synonym [ :foldl, :inject ]

In the current case, the definition for ++ in the Kernel module could
have an entry such as:

@synonym [ :append ]

If the relationship isn't close enough to rate the use of @synonym,
@see_also could be used. Armed with with this information, Elixir's
documentation tools could tell folks to look up append(), reduce(),
or whatever name has been selected. Users who feel strongly about a
given name (etc) can take steps to support it in their code.

Does this approach seem worthy of consideration? (ducks :-)

-r

--
http://www.cfcl.com/rdm Rich Morin r...@cfcl.com
http://www.cfcl.com/rdm/resume San Bruno, CA, USA +1 650-873-7841

Software system design, development, and documentation

[Peter Hamilton]

Just a note of technicality:

foldl and reduce are not the same thing (see monoids in Haskell if you really want to get deep on this). Elixir does have foldl in List.foldl. It's right next to List.foldr. Enum.reduce happens to be implemented as a foldl, but Enumerable does not require it to be so. Additionally, for unordered data types foldl/foldr do not make sense, which is likely why Enumerable calls it reduce instead.

Also, ++ is not append. It's concatenate. It functions as an append when the new element is wrapped in a list, and then concatenates that list with the current one.

--
You received this message because you are subscribed to the Google Groups "elixir-lang-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-ta...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-talk/B4AFFE81-3689-4A79-96F4-3C2596E37D47%40cfcl.com.

[Rich Morin]

On Jun 16, 2016, at 17:07, Peter Hamilton <petergh...@gmail.com> wrote:
> Just a note of technicality:
>

> foldl and reduce are not the same thing ...
>
> Also, ++ is not append. It's concatenate. ...

So, use @see_also (or whatever) when @synonym isn't quite appropriate.
The Unix man pages have been using this sort of approach for several
decades, so I think the basic idea is sound...

[Michał Muskała]

On 16 Jun 2016, at 18:43, Brad O'Hearne <brad.o...@gmail.com> wrote:

Users will always have the need to prepend, append, insert, replace, delete, clear, copy, etc. elements of a list. Those are logical needs of a list, a fundamental data structure, same as queues, stacks, etc. have their own needs. Take a stack for instance -- that is a fundamental data structure with canonical operations. 

I think this is the biggest misconception. A list has only two operations - prepend (cons) and take from front (hd/car) - and that’s it. Other operations are not native to lists and are constructed on top of those. The need to append, insert, replace, delete stems from treating lists as indexed arrays - but they are not!

And I know this, because I had this misconception as well. Lists are not arrays and generally every use of a list as an indexed structure is misusing it  (there are valid cases where you simply accept the fact that you’re misusing the list and that it won’t have a good support in the language or the runtime). There is most probably a much better data structure that will suit your needs. List is exactly like a stack from your example - you have a fundamental data structure with canonical operations - cons (push) and car (pop).

In my opinion the argument about leaky abstraction is not valid either. List is a data structure with specific properties (singly linked list), similar to how a map has specific properties (it’s unordered) and how every data structure you use has those properties. Hiding them or abstracting them is not helpful and can be damaging if you start to rely on those too much. You need to know your data structures.

Michał.

[Benjamin Scherrey]

A lot of this confusion is due to people using the term 'list' when
what they really have is something a lot more akin to a 'stack'.
However even an innocent query about this subject in a haskell irc
room, for example, will result in two days of flame wars so perhaps
best not to push the point too hard as they tend to overflow easily...
;-) Us old forthers really don't get caught up too much in such
things, we just liked being productive. Elixir seems to be on the
right path to that point as well which is why it's actually a useful
functional language for real-world problems.

-- Ben

> --
> You received this message because you are subscribed to the Google Groups
> "elixir-lang-talk" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to elixir-lang-ta...@googlegroups.com.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/elixir-lang-talk/64D52ECA-4715-4894-ACC5-12E5C46E903C%40muskala.eu.

[Bradley O'Hearne]

On Jun 16, 2016, at 11:36 PM, Benjamin Scherrey <sche...@proteus-tech.com> wrote:

A lot of this confusion is due to people using the term 'list' when
what they really have is something a lot more akin to a 'stack'.

You’re right on that point, and that’s good to bring upt, as the debate is turning to what operations are valid on a list, as if that general term has a single definition, which it doesn’t. I’ve generally seen “list” used as more of a general category of data structure which can vary by implementation, rather than one with a more specific canonical definition, such as stack or queue. A quick read of list on Wikipedia states pretty much the same thing: 

https://en.wikipedia.org/wiki/List_(abstract_data_type)

"The name list is also used for several concrete data structures that can be used to implement abstract lists…”

It also states clearly that append is a typical operation on a list. 

Current Elixir List operations have defined a logical List data structure that is able to be changed (regardless of the fact that individual nodes in the underlying implementation are immutable). If prepend element, insert element, delete element, replace element, etc are considered legit operations on this flavor of List, then it is odd to leave append element out. Taking off the propellor-hat and thinking about what that says in layman’s terms, it sounds extremely odd: 

“Elixir lists: you can add elements to the beginning of the list, delete elements anywhere in the list, replace elements anywhere in the last, you can flatten the list, pull off the front, pull off the end, and you can even add elements anywhere in the list, just not at the very end.” 

Now if that is the intent, as odd an non-intuitive as it sounds, then go for it. But it would be a good idea to document that clearly, because the need to append to a list is probably one of, if not the most common operation a developer is going to have on a list, given that “list” also implies order, and thus adding elements in order should be a frequent need. 

So to sum up my part in this thread — whatever the Elixir List is supposed to be, given the current state of documentation, the logical definition of the data structure isn’t completely intuitive, neither is the rationale for not having an append operation, nor is the accepted convention for appending to a list. I’d imagine many newcomers to Elixir have this same question at some point. 

Jose touched on all this in an earlier post….those would be good things to document somewhere. 

B

[Onorio Catenacci]

https://github.com/elixir-lang/elixir/wiki/FAQ#6-wheres-listappend

[Rickard Andersson]

Simply make a page like this one and be done with it:

https://wiki.haskell.org/How_to_work_on_lists

List.append would add pretty much nothing to the language and no matter how many times anyone says that this is somehow super common and supposedly the first thing people will be looking for, it doesn't change the fact that people actually using the language (or any typical functional programming language, for that matter) are not.

Maybe there should be a "please read me" box in tutorials saying: "Are you looking for List.append? It doesn't exist, and here is why. If you absolutely must append to a list, simply use the concatenation operator and be done with it, but know that appending to singly linked lists is inherently inefficient. Here's what to do instead."

But most of all, please don't generate 20 some e-mails long conversations about something that should've ended at "Yeah, appending to lists is a bad idea, this will be added to docs". People were informed why things are like they are and it could've just stopped at that, but instead it just keeps going on and on, like every thread where someone is convinced they know exactly what's best after having used the language for approximately 1 week.

[Bradley O'Hearne]

Just in time…another Elixir mailing list thread rescued from the jaws of friendly discourse….

To the specific point, the “added to docs’ conclusion wasn’t mine — that was Jose’s. I find it completely absurd to have an ordered data structure API which allows mutability but doesn’t formally allow and express adding elements in order. I consider it for this specific case inconsistent API design, and even though in this case the syntactical alternative was trivial, exposing underlying implementation details as an alternative I consider a bad principle to guide API design in general.

But that’s OK, that’s my opinion and my experience, and I get my input wasn’t of interest. No big deal. So great, let’s move on and get the thing documented so when questions arise again (and they will), someone won’t have to shoot the next messenger to come along and ask the question. Anyone with any vision for a community and truly interested in language adoption should extremely value having areas pointed out which are common intersections and places for confusion; and realize that its the well-worn paths that need paving the most, not someone continually yelling to “stay off the grass”.

In short — the repeated tack of shoot-the-messenger, declaring the poster as having no Elixir experience, a n00b, and not having knowledge worthy of questioning a design decision, roping off another “shall not be named” topic….can those few who can’t control the urge to be rude please just use the delete function of their mail client, rather than pollute what otherwise is a perfectly friendly conversation? The sudden thinning of skin every time a “why” question about design is asked…it just gives an appearance of not having the goods to back up a design decision with sound rationale….and more importantly….it isn’t friendly…doesn’t help engender a constructive spirit of community….

Smiles and grins….have a great weekend everyone….

Brad

> --
> You received this message because you are subscribed to the Google Groups "elixir-lang-talk" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-ta...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-talk/20160617194055.GA20862%40omniknight.

[Rickard Andersson]

> To the specific point, the “added to docs’ conclusion wasn’t mine — that was Jose’s.

Yes, wisely he saw the actual problem and was quick to address it.

> I find it completely absurd to have an ordered data structure API which allows mutability but doesn’t formally allow and express adding elements in order.

Lists are not mutable. Adding things to the end of a list is very possible, but doesn't need a special operator or function because it's not something you should be doing all that much. The concatenation operator should do fine. Use it.

> I consider it for this specific case inconsistent API design, and even though in this case the syntactical alternative was trivial, exposing underlying implementation details as an alternative I consider a bad principle to guide API design in general.

I wouldn't say it's inconsistent as much as the List module being slightly bloated. There are a few functions in there you probably never should use. Not because they're dangerous, but because you're not thinking properly about how to use lists. Once you start to use the indexes in a list and need to look up individual items in the list based on those indexes, or otherwise modify it based on them, you might want to structure your solution some other way.

> But that’s OK, that’s my opinion and my experience, and I get my input wasn’t of interest. No big deal. So great, let’s move on and get the thing documented so when questions arise again (and they will), someone won’t have to shoot the next messenger to come along and ask the question. Anyone with any vision for a community and truly interested in language adoption should extremely value having areas pointed out which are common intersections and places for confusion; and realize that its the well-worn paths that need paving the most, not someone continually yelling to “stay off the grass”.
>
> In short — the repeated tack of shoot-the-messenger, declaring the poster as having no Elixir experience, a n00b, and not having knowledge worthy of questioning a design decision, roping off another “shall not be named” topic….can those few who can’t control the urge to be rude please just use the delete function of their mail client, rather than pollute what otherwise is a perfectly friendly conversation? The sudden thinning of skin every time a “why” question about design is asked…it just gives an appearance of not having the goods to back up a design decision with sound rationale….and more importantly….it isn’t friendly…doesn’t help engender a constructive spirit of community….

I would like to stress that I don't represent some "greater Elixir community". I'm sorry for being rude to you.

Your e-mails don't come off as asking "Why?", but like most other threads of this kind they come off as asking "Why isn't this like _I_ want it to be?" and they don't end just at a clear and precise answer: They end when the OP has decided that he is done.

There is a rationale for the missing append operator/function and it's quite sound to most people working within this class of languages. I'm sorry if that rationale doesn't completely fly with you, but I don't think histrionics on the mailing list will change anything and arguing about it after a certain point is most likely meaningless.

// Rickard

[Robert Virding]

> I find it completely absurd to have an ordered data structure API which allows mutability but doesn’t formally allow and express adding elements in order.

Lists are not mutable. Adding things to the end of a list is very possible, but doesn't need a special operator or function because it's not something you should be doing all that much. The concatenation operator should do fine. Use it.

I just want to point out that there are no mutable data structures at all. None. So it is not just lists which are immutable but everything else as well. This means that if you are coming from an OO language you will find working with data quite different. This is nothing really erlang/elixir specific but is found in many functional languages. And that is not going to change.

It might be that this is not always mentioned everywhere as it is so basic that it is not always thought necessary to mention everywhere.

Robert

[Bradley O'Hearne]

For my part, there has never been any confusion on that point from the beginning, and that’s never been debated or questioned. The issue was the logical abstraction represented by the operations in the Elixir List API.

B

[Redvers Davies]

Bradley,

You said:

"I find it completely absurd to have an ordered data structure API which allows mutability but doesn’t formally allow and express adding elements in order."

You explicitly said mutable.  A clarification that there are no mutable data-structures on the beam seems an appropriate clarification.

--
You received this message because you are subscribed to the Google Groups "elixir-lang-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-ta...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-talk/2217968F-EF17-4688-BCB9-9179E986E55B%40bighillsoftware.com.

[Bradley O'Hearne]

Again….underlying implementation was never the issue. The operations in the List API are the issue. 

To clarify one last time (and this is the last for me) — the Elixir API provides these operations on a List which result in a list being returned which may be different from the original list (i.e. it . 

- prepend element (via operator)

- delete element

- delete element at any index

- flatten 

- flatten with tail (which happens to append the tail to the end of the list)

- fold left

- fold right

- insert element at any index

- key delete

- key replace

- key store

- replace element at any index

- concatenate list (via operator)

http://elixir-lang.org/docs/stable/elixir/List.html#summary

All in Elixir is immutable. That’s been understood from the beginning…from the first day I picked up Elixir. That was never the subject of this thread. I did use the word “mutability” — that was not referring to whether in its implementation the Elixir list data type itself could be changed. That was referring to the nature of the operations mentioned above, exposed on the Elixir List API, which give you the logical ability to start with a List which looks like X, and via one of the operations above, be handed back a List which looks like Y. 

If you are going to make the argument that my use of “mutability” was misused because the operations above return a new list, then all of the operations in the List API are misnamed, because they neither “delete element” or “insert element” or whatever technically either — they produce a new list (which wouldn’t be deleting or inserting or replacing either)— they would all be wrong on the basis of this immutability too. So if that’s your take, you need to go to the dev list and raise the issue of the above methods being improperly named, because they don’t do what they say either. That’s not my view, because I can separate API from implementation, but if you choose to raise the contention, then be consistent — your grievance exists in the entire existing List API. 

Looking at the list of operations above, I don’t know how anyone can argue with a straight face that “append” element doesn’t belong. But that’s not the view of others….that’s fine, agree to disagree. Doc it to help those who will be confused by the pretty obvious omission when they look for append in the List API. That’s better than nothing. 

That’s it for me. 

B