Need help/direction on how to implement datastructures (or if possible)

its about implementing linked list (and i have no clue how to implement actual datastructures)

I’m not sure I understand the question. What are you asking?

I guess its fine:
from what i understood in slack: you cant actually implement your own datastructures in elixir? so the exercise is just about understanding it and not actually implementing it, even if you just build on top of existing data structures

Programming languages supply their own basic data structures.
You build your data structures with the basic ones - including the protocol of operating on them.

Why does it feel wrong to use tuples?
Research the cons (“construct”) concept - now do tuples still feel wrong to you?

1 Like

It depends on what you mean with ‘implementing your own data structures’.

To be precise, you can build data structures, which means combining more simple data structures together into more complex ones, and implement algorithms, which might take zero or more data structures as input, check properties of these data structures, maybe alter them and then return zero or more altered data structures as output.

Of course, most data structures are built using an algorithm, a specific set of rules, to ensure that they will always be well-formed. In other words: To be sure that you can always ascertain certain properties from them. A linked list is one of these.

As for how to implement a linked list: Linked lists (to be precise, singly linked lists) are built-in in Elixir, so there is no need to build one on top of other data structures yourself.
Of course, to learn how they work, it is a great exercise to implement them yourself.

As for using a tuple or a struct to build your own variant: Both possibilities are completely fine. Underwater, a struct is also ‘just’ a map. It is however treated slightly special by Elixir, in the way that protocol dispatching (which is Elixir’s way of type classes) is done.

For a head scratching exercise, you can implement list in terms of lambda (https://en.wikipedia.org/wiki/Cons#Functional_Implementation)

Elixir translation
iex(19)> cons = fn h, t ->
...(19)>   fn f -> f.(h, t) end
...(19)> end
#Function<12.52032458/2 in :erl_eval.expr/5>

iex(20)> head = fn list ->
...(20)>   list.(fn h, _t -> h end)
...(20)> end
#Function<6.52032458/1 in :erl_eval.expr/5>

iex(21)> tail = fn list ->
...(21)>   list.(fn _h, t -> t end)
...(21)> end
#Function<6.52032458/1 in :erl_eval.expr/5>

iex(22)> list = cons.(1, cons.(2, cons.(3, nil)))
#Function<6.52032458/1 in :erl_eval.expr/5>

iex(23)> head.(list)
1
iex(24)> head.(tail.(list))
2
2 Likes