~technomancy/fennel

7 3

linked lists

Claude Marinier
Details
Message ID
<CAPg6usC86MnRqpQKPu_01hUoxt79qLCbM8Waqpkmj0uOTo8e_w@mail.gmail.com>
DKIM signature
pass
Download raw message
Bonjour,

Have you considered linked lists? If yes, what did you conclude?

    list = {next = list, value = v}

As a schemer, building things with cons and walking through lists with
car and cdr is comfortable and familiar. What is the corresponding
idiom in Fennel?

Merci.

P. S. Fennel is really cool! The portability and performance are great!

-- 
Claude Marinier
Details
Message ID
<CAAKhXobyXG26rrZ-N1Vo5X8bF=iWbPWm4C_=Fyyi_18aWb1owg@mail.gmail.com>
In-Reply-To
<CAPg6usC86MnRqpQKPu_01hUoxt79qLCbM8Waqpkmj0uOTo8e_w@mail.gmail.com> (view parent)
DKIM signature
pass
Download raw message
> Have you considered linked lists? If yes, what did you conclude?
>
>     list = {next = list, value = v}
>
> As a schemer, building things with cons and walking through lists with
> car and cdr is comfortable and familiar. What is the corresponding
> idiom in Fennel?

Fennel runs on Lua runtime, so we usually use Lua tables for all our
data structures.
And we also build custom data tructures based on Lua tables when we need!

You can have `first` and `rest` working on sequential tables like this:

(fn first [[x]] x)                      ; (first [1 2 3]) => 1
(fn rest [[_ & xs]] xs)                 ; (rest [1 2 3]) => [2 3]

However the main differences between Lua tables, and single linked
lists is that tables are mutable, and not persistent, while
single-linked lists are.
So if you need these properties you can build a list data type based on tables:

(fn cons [head tail]
  [head tail])

(cons 1 2)
;; => [1 2] - a pair like '(1 . 2) in scheme
(cons 1 (cons 2 (cons 3 4)))
;; => [1 [2 [3 4]]] - a list with cons on the end, as '(1 2 3 . 4) in scheme
(cons 1 (cons 2 (cons 3 nil)))
;; => [1 [2 [3]]], or '(1 2 3) in scheme

We can easilly write `car` and `cdr` to work on this list:

(fn car [[h]] h)
(fn cdr [[_ t]] t)

(car (cons 1 (cons 2 (cons 3 nil))))
;; => 1 (car on list returns its head)
(cdr (cons 1 2))
;; => 2 (pairs work as expected)
(car (cdr (cdr (cons 1 (cons 2 (cons 3 nil))))))
;; => 3 and you can chain them like in scheme no problem

Notice, that while `car` is exactly the same as `first` defined above,
`cdr` is different, because we return the existing tail, and not
construct a new table each time. Which means that our list is
persistent (but still mutable by obtaining reference)

As a final bonus point, we can make such lists print not as `[1 [2 [3
4]]]` but as `'(1 2 3 . 4)` and `[1 [2 [3]]]` as `'(1 2 3)`!
For this we need to use `__fennelview` metamethod, and metatables.
Metatables are beyond this discussion, and the implementation for list
is a bit long, but you can find it here:
https://andreyorst.gitlab.io/posts/2021-01-09-pretty-printing-for-fennel-language/#fennelview-metamethod
But beware that this is just a cosmetic change, you won't be able to
use the reader to read such lists back.

Hope this answers some questions you had!


-- 
Andrey Listopadov
Details
Message ID
<CAAKhXoYXMULO-ejMLrfafw38WCguG9hPkC-OLZeCUg6jK5QpTw@mail.gmail.com>
In-Reply-To
<CAPg6usC86MnRqpQKPu_01hUoxt79qLCbM8Waqpkmj0uOTo8e_w@mail.gmail.com> (view parent)
DKIM signature
pass
Download raw message
> What is the corresponding idiom in Fennel?

As for more idiomatic approach - Lua uses iterators for everything
related to tables.
There are `pairs` and `ipairs` functions which, when given a table
return iterators, that can be used in `each` special or `collect` and
`icollect` macros.

(each [key value (pairs {:a 1 :b 2})]
  (print key value))

This will walk the asoociative table `{:a 1 :b 2}` in an arbitrary
order, and print each key and its corresponding value.  The order is
arbitrary, because of how keys are hashed.

(each [i value (ipairs [10 20 30])]
  (print i value))

This will walk the sequential table `[10 20 30]` in the order of
specified elements, and print each elemen'ts index and value, startgin
from index  of 1.

And there are some macros that make some tasks a bit easier. For
example, Fennel has no `map` function, but it has `collect` and
`icollect` macros for building associative and sequential tables
respectively.  These have exactly the same syntax as `each` but return
a table as a result, while `each` is for side effects only.

Here's how you can use `icollect` and `collect` as `map` and `filter`:

(collect [key value (pairs {:a -1 :b 2 :c -3 :d 4})]
  (when (> value 0)
    (values key value)))
;; {:b 2 :d 4} -- the body works as filter only adding elements to the
resulting table that pass the test

(icollect [_ value (ipairs [1 2 3 4 5])]
  (* value value))
;; [1 4 9 16 25] -- each value was multiplied by itself, and added to
the resulting sequential table.

With these macros you can map and filter any kinds of tables.

A more recent addition is an `accumulate` macro that works as `foldl`:

(accumulate [res 0 _ value (ipairs [1 2 3 4])]
  (+ res value))
;; 10

You can find more info in the language reference
https://fennel-lang.org/reference

-- 
Andrey Listopadov
Claude Marinier
Details
Message ID
<CAPg6usBh3Gc92gP=-vaW29=x5ungawcDMvQ0ypVyPXLhe7uBcQ@mail.gmail.com>
In-Reply-To
<CAAKhXobyXG26rrZ-N1Vo5X8bF=iWbPWm4C_=Fyyi_18aWb1owg@mail.gmail.com> (view parent)
DKIM signature
pass
Download raw message
On Fri, 9 Jul 2021 at 03:06, Andrey Listopadov <andreyorst@gmail.com> wrote:
> > Have you considered linked lists? If yes, what did you conclude?
> >
> >     list = {next = list, value = v}
> >
> > As a schemer, building things with cons and walking through
> > lists with car and cdr are comfortable and familiar. What is
> > the corresponding idiom in Fennel?
>
> Fennel runs on Lua runtime, so we usually use Lua tables for
> all our data structures.

What would an idiomatic Fennel way of doing what I am used to
doing with lists? This is a more philosophical question. I look
at Fennel as a Lispy layer over Lua where lists are replaced
by tables. Is that "the Fennel way"?

> And we also build custom data structures based on Lua tables
> when we need!

That adds a lot of flexibility.

> You can have `first` and `rest` working on sequential tables like this:
>
> (fn first [[x]] x)                      ; (first [1 2 3]) => 1
> (fn rest [[_ & xs]] xs)                 ; (rest [1 2 3]) => [2 3]

This may be inefficient: I think Lua works better when adding &
removing to & from the end of a table.

> However the main differences between Lua tables, and single linked
> lists is that tables are mutable, and not persistent, while
> single-linked lists are.
> So if you need these properties you can build a list data type
> based on tables:
>
> (fn cons [head tail]
>   [head tail])
>
> (cons 1 2)
> ;; => [1 2] - a pair like '(1 . 2) in scheme
> (cons 1 (cons 2 (cons 3 4)))
> ;; => [1 [2 [3 4]]] - a list with cons on the end,
> ;;                    as '(1 2 3 . 4) in scheme
> (cons 1 (cons 2 (cons 3 nil)))
> ;; => [1 [2 [3]]], or '(1 2 3) in scheme

This is an approximation of a linked list. Might be useful in
some situations.

> We can easilly write `car` and `cdr` to work on this list:
>
> (fn car [[h]] h)
> (fn cdr [[_ t]] t)
>
> (car (cons 1 (cons 2 (cons 3 nil))))
> ;; => 1 (car on list returns its head)
> (cdr (cons 1 2))
> ;; => 2 (pairs work as expected)
> (car (cdr (cdr (cons 1 (cons 2 (cons 3 nil))))))
> ;; => 3 and you can chain them like in scheme no problem
>
> Notice, that while `car` is exactly the same as `first` defined
> above, `cdr` is different, because we return the existing tail,
> and not construct a new table each time. Which means that our
> list is persistent (but still mutable by obtaining reference)

I see the difference. So, when I really need a proper list, this
is the way.

Now if someone can address the philosophical question. :-)

Thank you.

-- 
Claude Marinier
Details
Message ID
<CAAKhXoaNhPtghKPBTCbzG4pM6TYf6yWsCn3bFc-qinG2_n8uYw@mail.gmail.com>
In-Reply-To
<CAPg6usBh3Gc92gP=-vaW29=x5ungawcDMvQ0ypVyPXLhe7uBcQ@mail.gmail.com> (view parent)
DKIM signature
pass
Download raw message
> What would an idiomatic Fennel way of doing what I am used to
> doing with lists? This is a more philosophical question. I look
> at Fennel as a Lispy layer over Lua where lists are replaced
> by tables. Is that "the Fennel way"?

Yes, tables and iterators are idiomatic in Fennel. But nothing stops
you from using lists if you want their characteristics, since lists
are useful in some situations. The Penlight [1] library has the List
class, but it is more like a Python list, rather Scheme list, but this
shows that you can extend the language with data types you need for a
particular case, so while idiomatic way is iterators, sometimes
non-idiomatic ways are required for efficiency :)

> > (fn cons [head tail]
> >   [head tail])
> >
> > (cons 1 2)
> > ;; => [1 2] - a pair like '(1 . 2) in scheme
> > (cons 1 (cons 2 (cons 3 4)))
> > ;; => [1 [2 [3 4]]] - a list with cons on the end,
> > ;;                    as '(1 2 3 . 4) in scheme
> > (cons 1 (cons 2 (cons 3 nil)))
> > ;; => [1 [2 [3]]], or '(1 2 3) in scheme
>
> This is an approximation of a linked list. Might be useful in
> some situations.

What makes you think this is an approximation and not a real linked list?

Linked list typically consists of a cell data structure, which holds
the value and the pointer to the next cell, and this is exactly what I
did there :)  It has time complexity characteristics of a linked list,
and you have to use `car` to get a value from it.  As for mutability,
it's common to create mutable lists in other languages, like C for
example, so immutability is an additional implementation property.

Here's another alternative - a purely functional linked list, which is
both persistent *and* immutable:

(fn cons [h t]
  (fn [ht] (if ht h t)))

(fn car [cell]
  (cell true))

(fn cdr [cell]
  (cell false))

(cons 1 2)                                   ; => '(1 . 2)
(car (cons 1 2))                             ; => 1
(cdr (cons 1 2))                             ; => 2
(cons 1 (cons 2 (cons 3)))                   ; => '(1 2 3)
(car (cons 1 (cons 2 (cons 3))))             ; => 1
(car (cdr (cdr (cons 1 (cons 2 (cons 3)))))) ; => 3

Such list uses closures and lambdas to store element values, which
makes it immutable, and the persistence comes naturally by storing
pointers to a functions.

Here's a reverse-list algorithm for example:

(fn reverse [list]
  ((fn reverse [list res]
     (if (= nil list)
         res
         (reverse (cdr list) (cons (car list) res))))
   list nil))

And just to demonstrate it, here's a function that prints our lists,
also written in a recursive way:

(fn print-list [list]
  (io.stdout:write "'(")
  ((fn print-list [list]
     (io.stdout:write (tostring (car list)))
     (when (cdr list)
       (io.stdout:write " ")
       (print-list (cdr list)))) list)
  (print ")"))

(local orig (cons 1 (cons 2 (cons 3))))

(print-list orig)                       ; => '(1 2 3)
(print-list (reverse orig))             ; => '(3 2 1)
(print-list orig)                       ; => '(1 2 3)

This reverse function will work with both purely-functional list, and
the table based list I've suggested before.

[1]: https://stevedonovan.github.io/Penlight/api/classes/pl.List.html

--
Andrey Listopadov
Details
Message ID
<043295d22c2b388ae93ae8ea6b3ba7b7@hagelb.org>
In-Reply-To
<CAPg6usBh3Gc92gP=-vaW29=x5ungawcDMvQ0ypVyPXLhe7uBcQ@mail.gmail.com> (view parent)
DKIM signature
permerror
Download raw message
Claude Marinier <claudem223@gmail.com> writes:

> What would an idiomatic Fennel way of doing what I am used to
> doing with lists?

In Fennel the main way you walk thru tables is using iterators as
mentioned; either `pairs` or `ipairs` usually: 
https://www.lua.org/pil/7.1.html

You can also walk thru a sequential table using recursion, but it will
look different from in Scheme:

     (fn recur [tbl ?i]
       (match (. tbl (or ?i 1))
         element (do (process-element element)
                     (recur tbl (+ (or ?i 1) 1)))))

This works because when you pattern match against a table lookup, the
`element` pattern will only match against non-nil values, so when you
reach a nil in the table, the function will no longer recurse. Having to
pass an index along every iteration is a little less smooth than car/cdr
but not too bad, I think.

> This is a more philosophical question. I look at Fennel as a Lispy
> layer over Lua where lists are replaced by tables. Is that "the Fennel
> way"?

Yes; Fennel is an improved notation for writing programs whose runtime
semantics are a subset of Lua's. Lua semantics are already remarkably
close to those of other lisp-family languages; lists vs tables being the
largest difference.

-Phil
Details
Message ID
<CAAKhXoaViE4v7vvzqS2s6fsE0zd_nyVZ9Hb90GQxFkF7XHtCxg@mail.gmail.com>
In-Reply-To
<CAPg6usC86MnRqpQKPu_01hUoxt79qLCbM8Waqpkmj0uOTo8e_w@mail.gmail.com> (view parent)
DKIM signature
pass
Download raw message
FYI I've made a library that implements Clojure vision of sequences
(linked lists) and lazy sequences:
https://github.com/andreyorst/lazy-seq. It's somewhat early to
announce this as a complete solution, but I'm working towards it. A
lot of functions from Clojure core namespace, which produce lazy
sequences seem to work just fine right now.

-- 
Andrey Listopadov

Re: lazy sequences (was: linked lists)

Claude Marinier
Details
Message ID
<CAPg6usBbkMtz8MJ8RUFtS50ER7iceFevHt=kSYNya3uvsz21pg@mail.gmail.com>
In-Reply-To
<CAAKhXoaViE4v7vvzqS2s6fsE0zd_nyVZ9Hb90GQxFkF7XHtCxg@mail.gmail.com> (view parent)
DKIM signature
pass
Download raw message
On Sun, 22 Aug 2021 at 12:34, Andrey Listopadov <andreyorst@gmail.com> wrote:
>
> FYI I've made a library that implements Clojure vision of sequences
> (linked lists) and lazy sequences:
> https://github.com/andreyorst/lazy-seq. It's somewhat early to
> announce this as a complete solution, but I'm working towards it. A
> lot of functions from Clojure core namespace, which produce lazy
> sequences seem to work just fine right now.

That is a lot of work. I find it a bit difficult to follow in places.
In some cases, using these will produce more clear solutions.

-- 
Claude Marinier
Reply to thread Export thread (mbox)