Parsing incoming TCP stream of Ascii chars, handle backspace char

Question

I need to parse input streams from a socket. The data is sent from a Telnet client, and thus I want to process incoming strings by finding the first '\r' character in the stream, then pick the bytes before the return char and finally process any backspace '\b' chars.

What would be the idiomatic way to deal with the '\b' bits in here? I'm currently using a mutable stack and push chars onto it, and if there is a backspace, I pop the last char. Then just turn the result into a string.

But I figure there is probably some nice way to do this with pattern matching and tail recursion. So, how can this be done the F# way?

let receiveInput (inputBuffer:StringBuilder) (received:Tcp.Received)=
    let text = Encoding.ASCII.GetString(received.Data.ToArray());
    inputBuffer.Append(text) |> ignore

    let all = inputBuffer.ToString()
    match all.IndexOf('\r') with
    | enter when enter >= 0 ->
        let textToProcess = all.Substring(0,enter)
        inputBuffer.Remove(0,enter+2) |> ignore

        //this is the part I'm wondering about
        let stack = new Stack<char>()
        for c in textToProcess do
            if c = '\b' then stack.Pop() |> ignore
            else stack.Push c

        let input = new System.String(stack |> Seq.rev |> Seq.toArray)

        Some(input)
    | _ ->
        None

Answer 1

Let's start by isolating the problematic part to a function:

open System
open System.Collections.Generic

let handleBackspaces textToProcess : string =
    let stack = Stack<char>()
    for c in textToProcess do
        if c = '\b' then stack.Pop() |> ignore
        else stack.Push c
    stack |> Seq.rev |> Seq.toArray |> String

This has a single mutable variable (stack). Whenever you have a mutating variable, you can replace it with an accumulator value in a recursive function. Here's one way to do it:

open System

let handleBackspaces' textToProcess : string =
    let rec imp acc = function
        | [] -> acc
        | '\b'::cs -> imp (acc |> List.tail) cs
        | c::cs -> imp (c::acc) cs
    textToProcess |> Seq.toList |> imp [] |> List.rev |> List.toArray |> String

You'll notice that I've called the accumulator value for acc. The imp function has the type char list -> char list -> char list, and it matches on the incoming char list: if it's empty, it returns the accumulator; if it has '\b' as the head, it removes the previous char from the accumulator by using List.tail; and in all other cases, it cons the first char to to accumulator and calls itself recursively.

Here's a (hopefully satisfactory) FSI session:

> handleBackspaces' "b\bfoo";;
val it : string = "foo"
> handleBackspaces' "foo";;
val it : string = "foo"
> handleBackspaces' "bar\bz";;
val it : string = "baz"
> handleBackspaces' "bar\b\boo";;
val it : string = "boo"
> handleBackspaces' "b\bfa\boo";;
val it : string = "foo"

Once one understands how to model something as a recursive function, it should be possible to implement it using a fold instead, as Ryan W Gough points out. Here's one way to do it:

let handleBackspaces'' textToProcess : string =
    textToProcess
    |> Seq.fold (fun acc c -> if c = '\b' then acc |> List.tail else c::acc) []
    |> List.rev
    |> List.toArray
    |> String