Looping Lists in F #

Question

Is it just me, or is F # not serving circular lists?

I looked at the FSharpList<T> class through a reflector and noticed that neither “structural equal” nor length methods check for loops. I can only guess if two such primitive functions do not check that most of the list functions will not do either.

If circular lists are not supported, why?

thanks

PS: Do I even consider the right list class?

Answer 1

In F # there are many different lists / types of collections.

• F # list As Chris said, you cannot initialize a recursive value of this type, because the type is not lazy and not changed (immutability means you need to create it immediately, and the fact that it is not lazy means you cannot use recursive F # values ​​using let rec ). As ssp said, you can use Reflection to hack it, but this is probably the case we don't want to discuss.

• The other type is seq (actually IEnumerable ) or the LazyList type from PowerPack. They are lazy, so you can use let rec to create a circular value. However (as far as I know), none of the functions working with them takes into account circular lists - if you create a circular list, it simply means that you create an infinite list, so the result (for example) of the map will be a potentially infinite list.

Here is an example for a LazyList type:

  #r "FSharp.PowerPack.dll" // Valid use of value recursion let rec ones = LazyList.consDelayed 1 (fun () -> ones) Seq.take 5 l // Gives [1; 1; 1; 1; 1] 

The question is what data types you can define yourself. Chris shows the modified list, and if you write operations that modify it, they affect the entire list (if you interpret it as an infinite data structure).

You can also define a lazy (potentially circular) data type and implement operations that process loops, so when you create a circular list and project it into another list, it will create a circular list (rather than a potentially infinite data structure).

A type declaration may look like this (I use an object type, so that we can use reference equality when checking for loops):

 type CyclicListValue<'a> = Nil | Cons of 'a * Lazy<CyclicList<'a>> and CyclicList<'a>(value:CyclicListValue<'a>) = member x.Value = value 

The following map function handles loops - if you give it a loop list, it will return a newly created list with the same loop structure:

 let map f (cl:CyclicList<_>) = // 'start' is the first element of the list (used for cycle checking) // 'l' is the list we're processing // 'lazyRes' is a function that returns the first cell of the resulting list // (which is not available on the first call, but can be accessed // later, because the list is constructed lazily) let rec mapAux start (l:CyclicList<_>) lazyRes = match l.Value with | Nil -> new CyclicList<_>(Nil) | Cons(v, rest) when rest.Value = start -> lazyRes() | Cons(v, rest) -> let value = Cons(fv, lazy mapAux start rest.Value lazyRes) new CyclicList<_>(value) let rec res = mapAux cl cl (fun () -> res) res 

Answer 2

The list type F # is essentially a linked list, where each node has a "next". This theoretically allows you to create loops. However, F # lists are immutable. Thus, you can never "make" this cycle a mutation, you will have to do this during construction. (Since you could not update the last node to move forward.)

You can write this to do this, however the compiler specifically prevents this:

  let rec x = 1 :: 2 :: 3 :: x;; let rec x = 1 :: 2 :: 3 :: x;; ------------------------^^ stdin(1,25): error FS0260: Recursive values cannot appear directly as a construction of the type 'List`1' within a recursive binding. This feature has been removed from the F# language. Consider using a record instead. 

If you want to create a loop, you can do the following:

 > type CustomListNode = { Value : int; mutable Next : CustomListNode option };; type CustomListNode = {Value: int; mutable Next: CustomListNode option;} > let head = { Value = 1; Next = None };; val head : CustomListNode = {Value = 1; Next = null;} > let head2 = { Value = 2; Next = Some(head) } ;; val head2 : CustomListNode = {Value = 2; Next = Some {Value = 1; Next = null;};} > head.Next <- Some(head2);; val it : unit = () > head;; val it : CustomListNode = {Value = 1; Next = Some {Value = 2; Next = Some ...;};} 

Answer 3

The answer is the same for all languages ​​with support for tail call optimization and support for first-class functions (function types): it emulates cyclic structures so easily.

 let rec x = seq { yield 1; yield! x};; 

The simplest way to emulate this structure is using laziness sec. Of course, you can hack a list view as described here .

Answer 4

As already mentioned, your problem is that the list type is immutable, and for list is circular, which you will need to bind to its last element so that it does not work, Of course, you can use sequences.

If you have an existing list and want to create an infinite sequence on top of it that cycles through the elements of the list, here's how you could do it:

 let round_robin lst = let rec inner_rr l = seq { match l with | [] -> yield! inner_rr lst | h::t -> yield h yield! inner_rr t } if lst.IsEmpty then Seq.empty else inner_rr [] let listcycler_sequence = round_robin [1;2;3;4;5;6]