How to interweave state with list

[jwilliamson1]

The following exercise (from Pragmatic Programmer) reads instructions from a text file and draws the results on a canvas. The authors suggest using Yacc but I thought it would be fun to try it with parsec in Language-Ext and that part was a breeze. But I ran into some problems generating the points to draw to the screen in a functional manner and was looking for some assistance in this area.

The commands in instruction.txt are
D
P 5
S 2
S 10
E 30
N 5
W 2
U

D = pen down on canvas
P n = set brush stroke size to n
S n = south n paces
E n = east n paces
N n = up n paces
W n = left n paces
U = pen up off canvas

using System.Collections.Generic;
using System.Windows;
using System.Windows.Ink;
using System.Windows.Input;
using LanguageExt;
using LanguageExt.ClassInstances;
using static LanguageExt.Prelude;
using static System.Console;
using static System.IO.File;
using static PenApp.Parsers;
using static PenApp.SeqExt;
using static PenApp.InterpretCommands;

namespace PenApp
{
    /// <summary>
    /// Interaction logic for MainWindow.xaml
    /// </summary>
    public partial class MainWindow : Window
    {
        public delegate Seq<SpecificPoint> GeneratePoints(Seq<Cmd> cmd);

        public delegate Either<string, Seq<Cmd>> ParseCmdsDel(string text);

        public delegate Unit WriteDel(Seq<SpecificPoint> seqs);

        public delegate string ReadDel(string path);
        public MainWindow()
        {
            InitializeComponent();

            ReadDel readAllText = ReadAllText;
            ParseCmdsDel parseCommands = ParseCommands;
            WriteDel writePoints = WritePoints;
            Seq<SpecificPoint> GeneratePoints(Seq<Cmd> cmds) => mapAccumL(InterpretCmds, SpecificPoint.Default(), cmds).results.Flatten();

            var result = Run(readAllText, parseCommands, writePoints, GeneratePoints);

            result.Match((_) => WriteLine("Success"), WriteLine);
        }

        public Either<string, Unit> Run(ReadDel readAllText, ParseCmdsDel parseCommands, WriteDel writePoints,
            GeneratePoints generatePoints)
        {
            var text = readAllText("Instructions.txt");

            var res = 
                from cmds in parseCommands(text)
                let pts = generatePoints(cmds)
                select writePoints(pts);

            return res;
        }

        public virtual Unit WritePoints(Seq<SpecificPoint> seqs)
        {
            foreach (var s in seqs)
            {
                this.inkCanvas1.Strokes.Add(
                    new Stroke(new StylusPointCollection(new List<Point> { s.Point }), new DrawingAttributes(){Height = s.BrushSize, Width = s.BrushSize}));

            }
            return unit;
        }
    }
}

namespace PenApp
{
    public abstract class Cmd { }

    public class StrokeSize : Cmd
    {
        public StrokeSize(int size)
        {
            this.Size = size;
        }

        public int Size { get; }
    }
    public class PenUp : Cmd { }

    public class PenDown : Cmd { }

    public enum Directions { North, South, East, West }

    public class Direction : Cmd
    {
        public Directions Value { get; set; }
        public Direction(char direction)
        {
            switch (direction)
            {
                case 'N':
                    this.Value = Directions.North;
                    break;
                case 'S':
                    this.Value = Directions.South;
                    break;
                case 'E':
                    this.Value = Directions.East;
                    break;
                default:
                    this.Value = Directions.West;
                    break;
            }
        }
    }

    public class Move : Cmd
    {
        public Move(int moves, Direction direction)
        {
            this.Paces = moves;
            this.Direction = direction.Value;
        }

        public int Paces { get; }
        public Directions Direction { get; }

    }
}

using System;
using System.Collections.Generic;
using System.Text;
using System.Windows;

namespace PenApp
{
    public class SpecificPoint
    {
        public readonly Point Point;
        public readonly bool Draw;
        public readonly int BrushSize;
        public SpecificPoint(Point point, bool draw, int brushSize)
        {
            Point = point;
            Draw = draw;
            BrushSize = brushSize;
        }

        public static SpecificPoint Default()
        {
            return new SpecificPoint(new Point(0, 0), false, 2);
        }

        public SpecificPoint With(Point? Point = null, bool? Draw = null, int? BrushSize = null) => new SpecificPoint(Point ?? this.Point, Draw ?? this.Draw, BrushSize ?? this.BrushSize);
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using LanguageExt;
using System.Windows;
using LanguageExt;
using static LanguageExt.Prelude;

namespace PenApp
{
    public static class InterpretCommands
    {

        public static (SpecificPoint, Seq<SpecificPoint>) InterpretCmds(SpecificPoint specificPoint, Cmd cmd)
        {
            switch (cmd)
            {
                case PenUp pup:
                    return (PenUpHandler(pup, specificPoint), List(PenUpHandler(pup, specificPoint)).ToSeq());
                case PenDown pdown:
                    return (PenDownHandler(pdown, specificPoint), List(PenDownHandler(pdown, specificPoint)).ToSeq());
                case StrokeSize size:
                    return (StrokeSizeHandler(size, specificPoint), List(StrokeSizeHandler(size, specificPoint)).ToSeq());
                case Move move:
                    return MoveHandler(move, specificPoint);

            }
            throw new InvalidOperationException("Should never get here");
        }

        public static SpecificPoint PenUpHandler(PenUp cmd, SpecificPoint specPoint) =>
            specPoint.With(Draw: false);

        public static SpecificPoint PenDownHandler(PenDown cmd, SpecificPoint specPoint) =>
            specPoint.With(Draw: true);

        public static SpecificPoint StrokeSizeHandler(StrokeSize cmd, SpecificPoint specificPoint) =>
            specificPoint.With(BrushSize: cmd.Size);

        public static (SpecificPoint, Seq<SpecificPoint>) MoveHandler(Move cmd, SpecificPoint specificPoint)
        {
            var curX = (int)specificPoint.Point.X;
            var curY = (int)specificPoint.Point.Y;
            var paces = cmd.Paces;

            switch (cmd.Direction)
            {
                case Directions.South:
                    return (specificPoint.With(Point: new Point(curX, curY + paces)), Enumerable.Range(curY, paces).Map(y => specificPoint.With(Point: new Point(curX, y)))
                        .ToSeq());
                case Directions.East:
                    return (specificPoint.With(Point: new Point(curX + paces, curY)), Enumerable.Range(curX, paces).Map(x => specificPoint.With(Point: new Point(x, curY)))
                        .ToSeq());
                case Directions.North:
                    return (specificPoint.With(Point: new Point(curX, curY - paces)), Enumerable.Range(-1 * curY, paces).Map(y => specificPoint.With(Point: new Point(curX, Math.Abs(y))))
                        .ToSeq());
                default:
                case Directions.West:
                    return (specificPoint.With(Point: new Point(curX - paces, curY)), Enumerable.Range(-1 * curX, paces).Map(x => specificPoint.With(Point: new Point(Math.Abs(x), curY)))
                        .ToSeq());
            }
        }
    }
}

using System;
using System.Collections.Generic;
using LanguageExt;
using LanguageExt.Parsec;
using static LanguageExt.Prelude;
using static LanguageExt.Parsec.Prim;
using static LanguageExt.Parsec.Char;
using static LanguageExt.Parsec.Expr;
using static LanguageExt.Parsec.Token;
using static System.Console;


namespace PenApp
{
    public static class Parsers
    {
        public static Either<string, Seq<Cmd>> ParseCommands(string text)
        {
            //parsers
            var strokeSize = from p in ch('P')
                from sp in space
                from n in asString(many1(digit))
                select new StrokeSize(Int32.Parse(n)) as Cmd;

            var penUp = from p in ch('U')
                select new PenUp() as Cmd;

            var penDown = from p in ch('D')
                select new PenDown() as Cmd;

            var direction = from d in oneOf("NSWE")
                from sp in space
                from n in asString(many1(digit))
                select new Move(Int32.Parse(n), new Direction(d)) as Cmd;

            var twoPartCmd = either(strokeSize, direction);

            var penCmds = either(penUp, penDown);

            var anyCmd = either(penCmds, twoPartCmd);

            var line = from c in anyCmd
                from l in either(eof, endOfLine.Map(_ => unit))
                select c;

            var result = parse(many1(line), text);

            return result.ToEither();

            //var interpreted = from cmds in result.ToEither()
            //  select Interpret(cmds);

            //return interpreted;
        }

        static Either<string, Unit> Interpret(Seq<Cmd> cmds)
        {
            cmds.Map((cmd) =>
            {
                switch (cmd)
                {
                    case PenUp pup:
                        WriteLine("Pen up");
                        break;
                    case PenDown pdown:
                        WriteLine("Pen Down");
                        break;
                    case Move mv:
                        WriteLine($"Move {mv.Paces} to the {mv.Direction}");
                        break;
                    case StrokeSize size:
                        WriteLine($"Change brush stroke size to {size.Size}");
                        break;
                    default:
                        Left("Unable to intepret");
                        break;
                }
                return unit;
            });
            return Right(unit);
        }
    }
}

Finally these 3 extension methods are my various attempts at functionally generating points by taking an initial default specificPoint state of (x =0, y =, pendown = false, brushsize =2). This state is combined with the current list element which creates a new starting state for the next element and also creates a new list, as the current new element, that get flatten later. I am currently using the first imperative approach with mutation, but I want to know if there is a better way to do this?

Also what if my InterpetCmds method had to handle out of bounds points? For example if the instructions say to move left beyond the y axis like y = -1. I would like to return an either in this case. And have the whole process stop? How could I get this to work in my mapAccuml or some other functional technique?

So if my signature is like this public static Either<string, (SpecificPoint, Seq<SpecificPoint>)> InterpretCmds(SpecificPoint specificPoint, Cmd cmd), is there a way to have the mapAccuml or some other method short circuit? In haskell is the left side of the mapAccuml tuple evaluated lazily and does that make using traverse on that list more effecient than is possible in C#?

[louthy]

First make your InterpretCommands return an Either<Error, ...> for all its operations. That will allow you to report errors:

public static class InterpretCommands
{
    public static Either<Error, (SpecificPoint Current, Seq<SpecificPoint> Points)> InterpretCmds(SpecificPoint specificPoint, Cmd cmd) => cmd switch
    {
        PenUp pup       => from r in PenUpHandler(pup, specificPoint)
                           select (r, Seq1(r)),

        PenDown pdown   => from r in PenDownHandler(pdown, specificPoint)
                           select (r, Seq1(r)),

        StrokeSize size => from r in StrokeSizeHandler(size, specificPoint)
                           select (r, Seq1(r)),

        Move move       => MoveHandler(move, specificPoint),

        _               => Error.New("Invalid operation")
    };

    public static Either<Error, SpecificPoint> PenUpHandler(PenUp cmd, SpecificPoint specPoint) =>
        specPoint.With(Draw: false);

    public static Either<Error, SpecificPoint> PenDownHandler(PenDown cmd, SpecificPoint specPoint) =>
        specPoint.With(Draw: true);

    public static Either<Error, SpecificPoint> StrokeSizeHandler(StrokeSize cmd, SpecificPoint specificPoint) =>
        specificPoint.With(BrushSize: cmd.Size);

    public static Either<Error, (SpecificPoint, Seq<SpecificPoint>)> MoveHandler(Move cmd, SpecificPoint specificPoint)
    {
        var curX = (int)specificPoint.Point.X;
        var curY = (int)specificPoint.Point.Y;
        var paces = cmd.Paces;

        return cmd.Direction switch
        {
            Directions.South => Interpolate(specificPoint, new Point(curX, curY + paces)),
            Directions.East  => Interpolate(specificPoint, new Point(curX + paces, curY)),
            Directions.North => Interpolate(specificPoint, new Point(curX, curY - paces)),
            _                => Interpolate(specificPoint, new Point(curX - paces, curY))
        };
    }

    static double MakeUnit(double x) =>
        x < 0 ? -1
      : x > 0 ? 1
      : 0;

    static Either<Error, (SpecificPoint, Seq<SpecificPoint>)> Interpolate(SpecificPoint origin, Point destination)
    {
        var dx = MakeUnit(destination.X - origin.Point.X);
        var dy = MakeUnit(destination.Y - origin.Point.Y);
        var current = new Point(origin.Point.X, origin.Point.Y);

        IEnumerable<Either<Error, SpecificPoint>> Yield()
        {
            while(current.X != destination.X || current.Y != destination.Y)
            {
                current.X += dx;
                current.Y += dy;
                    
                yield return current.X < 0 ? Left(Error.New("X out of bounds"))
                           : current.Y < 0 ? Left(Error.New("Y out of bounds"))
                           : Right<Error, SpecificPoint>(origin.With(Point: new Point(current.X, current.Y)));
            }
        }

        return from pts in Yield().Sequence()
               select (origin.With(Point: destination), pts.ToSeq().Strict());
    }
}

I've done some refactoring to use C#8 switch expressions rather than the old switch statements. I've also broken out the Enumerable.Range into its own Interpolate function, the original was buggy I think, or at least hard to follow.

Next in MainWindow.xaml.cs the delegates need updating to all return Either<Error, ...>

public delegate Either<Error, Seq<SpecificPoint>> GeneratePoints(Seq<Cmd> cmd);
public delegate Either<Error, Seq<Cmd>> ParseCmdsDel(string text);
public delegate Either<Error, Unit> WriteDel(Seq<SpecificPoint> seqs);
public delegate Either<Error, string> ReadDel(string path);

Replace the delegates assignment with:

ParseCmdsDel parseCommands = ParseCommands;
WriteDel writePoints = WritePoints;

Either<Error, string> ReadText(string path) =>
    Try(() => ReadAllText(path)).ToEither().MapLeft(Error.New);

That wraps up the file-reading, so that any exceptions get converted into the common Error format.

GeneratePoints can now be updated to use FoldWhile. Which aggregates state over a collection, but also has a predicate which allows for early-out (which we'll use whenever we get an Error):

Either<Error, Seq<SpecificPoint>> GeneratePoints(Seq<Cmd> cmds) =>
    cmds.FoldWhile(InitialState,
                (state, cmd) => from s in state
                                from r in InterpretCmds(s.Current, cmd)
                                select (r.Current, s.Points + r.Points),
                state => state.IsRight)
        .Map(state => state.Points);

It takes an initial state:

static Either<Error, (SpecificPoint Current, Seq<SpecificPoint> Points)> InitialState =>
    Right((SpecificPoint.Default, Seq<SpecificPoint>()));

Finally, Run can be updated to leverage the fact that all the delegates return an Either<Error, ...>:

public Func<string, Either<Error, Unit>> Run(
    ReadDel readAllText, 
    ParseCmdsDel parseCommands, 
    WriteDel writePoints,
    GeneratePoints generatePoints) =>
        path =>
            from text in readAllText(path)
            from cmds in parseCommands(text)
            from pts  in generatePoints(cmds)
            from resu in writePoints(pts)
            select resu;

Notice how the result is a Func<string, ...>. This allows us to compose all the parts of the runner once and reuse it:

    var runner = Run(ReadText, parseCommands, writePoints, GeneratePoints);

It can then be called with the injected path name:

     var result = runner("Instructions.txt");

Other things to note:

• Use Seq1(x) to create single item Seq<A> types. This is a legacy of the Seq method being used to induce other types into enumerables.
• In Parsec. Use attempt(x) where you have either(x, y), that will protect against partial parsing causing a failure of the whole file to parse. Same for choice(x, y, z, ...); wrap each parser with attempt(p) apart from the last one. This can also be useful in the parsers that parse sequences, like many

I have posted my fully working code to: https://gist.github.com/louthy/a09f660b1b2543d1784758eb2acf7504

[jwilliamson1]

Awesome. I was just looking for some direction, but this really helps. The FoldWhile is very cool. I was wondering what the reason for the Strict() call in InterpretCommands. I see that without the call we just sit at the line this.inkCanvas1.Strokes.Add( new Stroke(new StylusPointCollection(new List<Point> { s.Point }), new DrawingAttributes() { Height = s.BrushSize, Width = s.BrushSize }));.

The reusable runner is nice too. I will try to get a bunch of files drawing.

[louthy]

Strict() forces evaluation which makes finite lists faster to process later (iteration etc.); it shouldn't pause, so that might highlight a bug in the lazy seq, so I'll do a bit of digging on that.

[jwilliamson1]

I probably should have opened a separate issue but I wanted to keep the context together, I changed the main method of the program to exploit using the reusable runner from above. Now the program takes multiple instruction files and run them using apply so that if one fails the others keep writing.

Anway, the following code works
`public MainWindow()
{
InitializeComponent();

        ParseCmdsDel parseCommands = ParseCommands;
        WriteDel writePoints = WritePoints;

        Either<Error, string> ReadText(string path) =>
            Try(() => ReadAllText(path)).ToEither().MapLeft(Error.New);

        Either<Error, Seq<SpecificPoint>> GeneratePoints(Seq<Cmd> cmds) =>
            cmds.FoldWhile(InitialState,
                      (state, cmd) => from s in state
                                      from r in InterpretCmds(s.Current, cmd)
                                      select (r.Current, s.Points + r.Points),
                      state => state.IsRight)
                .Map(state => state.Points);

        var runner = Run(ReadText, parseCommands, writePoints, GeneratePoints);

        var fileNames = Seq("Instructions.txt", "Instructions0.txt", "Instructions2.txt");

        var results = filesNames.Fold(InitialRunnerState, (state, file) => state.Apply(_ => runner(file)));

        results.Match(
            Right: _ => Trace.WriteLine("Success"),
            Left: e => Trace.WriteLine(e));
    }

`

However if I change the declaration and setting of fileNames to the following then nothing runs.
var fileNames = new Seq<string>{"Instructions.txt", "Instructions0.txt", "Instructions2.txt"};

[louthy]

Use:

 var fileNames = Seq("Instructions.txt", "Instructions0.txt", "Instructions2.txt");

The other form of construction I think calls Add which works for mutable types, but not for immutable ones that return a new value. I'll need to do some digging to be sure.

[louthy]

Following up on the collection initialisation approach used. It appears that it's a limitation of C# that any Add function is called regardless of whether it returns a value or not, and it discards the return value. That means it can't be used to construct an immutable collection.

I have raised the issue on the csharplang github repo. But, for now, just consider it to not work and construct with the constructor function I mention above.

[jwilliamson1]

Will do. Thanks for looking into this!