Immutability in C# Part Four: An Immutable Queue

re: Immutability in C# Part Four: An Immutable Queue

yy17yy — Wed, 26 Sep 2012 08:47:31 GMT

i don't think this is O(1).

assume q=1,1,1,1,1,1,...................1,1,1(10000total), then for(int i=0;i<10000;++i){q.enqueue(1).dequeue();}

O(n)

re: Immutability in C# Part Four: An Immutable Queue

Johan De Jong — Sun, 03 Jun 2012 17:10:24 GMT

Eric

Since the backward Queue doesn't change, in dequeue operations, when we have say forward queue {1,2,3}, backward queue {4,3,2,1} after enqueue of 4, the dequeues would be {2,3} and {4,3,2,1} , then {3} and {4,3,2,1} and finally {} and {4,3,2,1} at which point we reverse the backward {1,2,3,4} and {} would be the state. Now when you dequeue you will get 1 instead of 4?

re: Immutability in C# Part Four: An Immutable Queue

Farhan Ali — Sat, 23 Feb 2008 09:34:52 GMT

i know there is some mistake in making student data using linklist please solve this problem .

////////////////////////////////////////////////

using System;

namespace ConsoleApplication10

{

/// Summary description for Class1.

class Class1

{

static void newdata()

{

Console.WriteLine("Successfull");

Console.ReadLine();

}

static void display()

{

Console.WriteLine("There is nothing to Display.");

Console.ReadLine();

}

//static void e_exit()

//{

// }

[STAThread]

static void Main(string[] args)

{

string input;

Console.WriteLine ("Student Record");

Console.WriteLine ("==============");

Console.WriteLine ("a- Enter Data ." );

Console.WriteLine ("b- Display Data ." );

Console.WriteLine ("c- Exit." );

input = Console.ReadLine();

switch(input)

{

case "a" : newdata();break;

case "b" : display();break;

// case c : e_exit();

}

main();

Console.ReadLine();

}

re: Immutability in C# Part Four: An Immutable Queue

Eric Lippert — Tue, 22 Jan 2008 17:56:10 GMT

There are three possible cases:

1) Singly linked list with links pointing back to front. How are you going to efficiently "back up" the front pointer on dequeue?

2) Singly linked list with links pointing front to back. How are you going to enqueue on the back pointer without mutating the current back link? That link is immutable.

3) Doubly linked list -- same problem as #2; you have to mutate state.

Linked lists make great mutable queues. The goal of this series is to describe how to make immutable data structures.

re: Immutability in C# Part Four: An Immutable Queue

Tue, 22 Jan 2008 12:58:50 GMT

can someone explain why you wouldn't use a linked list with a front pointer to the next item to be dequeued and a back pointer to the last item queued?

Immutability in C#

Sat, 19 Jan 2008 00:04:55 GMT

For some reason, there's been a lot of buzz lately around immutability in C#. If you're interested in

re: Immutability in C# Part Four: An Immutable Queue

phreno — Mon, 31 Dec 2007 23:54:38 GMT

I got thinking about immutability when I was trying to use Enums to create lists of things the IDE recognized. As you know,

Example:

public Enum fruitType

{

Apple,

Orange,

Pear

}

This is so much better than creating lists of things that the IDE doesn't recognize, i.e. Hashtable dictionaries.

public Hashtable fruitTypeHT = new Hashtable ();

fruitTypeHT["Apple"] = null;

fruitTypeHT["Orange"] = null;

fruitTypeHT["Pear"] = null;

In the case of the Enumerated list, if you wish to change Pear to AsianPear it is simple to use the refactoring to rename all instances of Pear to AsianPear. There is no such help for the Hashtable version, plus, it is possible to still modify the hashtable dictionary contents during run-time.

It would be fantastic if we could have "popsicle" Enums then we could fill them from the database during program startup, yet still refer to concrete items in the Enum list in the code. I know this may seem like wanting to have your cake and eat it too; maybe so. But this is the basic difficulty with working with meta-data that is held in database tables. Your code has to refer to specific items of meta-data, but you want a way to easily find or change all specific instances referenced. This would be a great problem to solve, and I am convinced immutability will be a key part of the solution.

One thing I tried to my hand at was creating an Immutable Hashtable and an Immutable ArrayList. They are wrappers for standard Hashtables and ArrayLists, but there is a makeReadOnly () method in each that freezes the list from that point on. I use this to handle some forms of meta-data from the database, where I don't want my program to ever attempt to change or add items to the list pulled from the DB.

http://www.codeproject.com/KB/cs/ImmutableHashtable.aspx

http://www.codeproject.com/KB/cs/ImmutableArrayList.aspx

What do we have to do to get MS to beef up Enums? I'm already standing on my head!!

re: Immutability in C# Part Four: An Immutable Queue

Sebastian Sylvan — Thu, 27 Dec 2007 20:20:25 GMT

Eric,

Two features that would make this sort of thing easier would be case classes a la Scala, and pattern matching. That way you could write Haskell style algebraic data types easily without all that boiler plate.

re: Immutability in C# Part Four: An Immutable Queue

Serge Sitnikov — Wed, 26 Dec 2007 14:21:18 GMT

There is a little mess with immutable and lock-free structures in comments. It is a different things. Immutable structures are thread safe utilizing the "don't worry about it" principle, but they don't provide the data coherency. Lock-free structures are thread safe by the same mean and also coherent.

re: Immutability in C# Part Four: An Immutable Queue

Eric Lippert — Mon, 24 Dec 2007 21:36:53 GMT

No, the problem is that you are narrowly defining what you mean by "reliable in a mulithreaded environment". You are defining 'reliable' to mean 'two threads can enqueue "the same" queue and both enqueued items are present in the resulting queue. This is a very "procedural programming" way to think about thread safety -- thread safety is PRESERVATION OF ALL SIDE EFFECTS.

If that's the kind of reliability you want then you should probably be using a mutable threadsafe queue! If you try to use an immutable queue for this purpose then essentially you will have to synchronize access not to the queue -- the queue is threadsafe -- but to the variable which contains the "canonical" version of the queue.

Immutable queues provide a _different_ kind of reliability, namely "two threads can enqueue the same queue at the same time, and the result on each thread is NOT polluted by the result on the other." This is a very functional programming way of thinking about thread safety -- thread safety is IMMUNITY FROM SIDE EFFECTS. Enqueueing X onto queue Q1 should result in the queue which is Q1 plus X, always, independent of any nonsense happening to Q1 on another thread.

Once you embrace a world where side effects are to be eliminated, not preserved, things get much easier to reason about.