Visit the reverse-string exercise on Exercism to read the full instructions and download the exercise files.
Dig Deeper
Seq module
Seq module
module ReverseString
let reverse input =
input
|> Seq.rev
|> Seq.toArray
|> System.String
The string class implements the seq interface (which is an abbreviation of the CLI IEnumerable interface), which means we can use functions from the Seq module on it.
First, we pipe the input string into Seq.reverse, which returns an enumerable with the input in reverse order.
To convert the seq<char> returned by Seq.reverse back to a string, we first use Seq.toArray to convert it to a char[].
Finally, we convert the char array back to a string by piping it into the System.String constructor.
Span
Span<T>
module ReverseString
open System
open Microsoft.FSharp.NativeInterop
let reverse (input: string) =
let memory = NativePtr.stackalloc<byte>(input.Length) |> NativePtr.toVoidPtr
let span = Span<char>(memory, input.Length)
for i in 0..input.Length - 1 do
span[input.Length - 1 - i] <- input[i]
span.ToString()
F# 4.5 introduced support for the Span<T> class, which was specifically designed to allow performant iteration/mutation of array-like objects.
The Span<T> class helps improve performance by always being allocated on the stack, and not the heap.
As objects on the stack don’t need to be garbage collected, this can help improve performance (check this blog post for more information).
How can we leverage Span<T> to reverse our string?
The string class has an AsSpan() method, but that returns a ReadOnlySpan<char>, which doesn’t allow mutation (otherwise we’d be able to indirectly modify the string).
We can work around this by manually allocating a char[] and assigning to a Span<char>:
let array = Array.zeroCreate<char>(input.Length)
let span = Span<char>(array)
for i in 0..input.Length - 1 do
span[input.Length - 1 - i] <- input[i]
span.ToString()
After creating Span<char>, we use a regular for-loop to iterate over the string’s characters and assign them to the right position in the span.
Finally, we can use the string constructor overload that takes a Span<char> to create the string.
However, this is basically the same approach as the Array.Reverse() approach, but with us also having to manually write a for-loop.
We can do one better though, and that is to use [NativePtr.stackalloc]nativeptr.stackalloc.
With stackalloc, we can assign a block of memory on the stack (whereas the array would be stored on the heap).
let memory = NativePtr.stackalloc<byte>(input.Length) |> NativePtr.toVoidPtr
let span = Span<char>(memory, input.Length)
With this version, the memory allocated for the Span<char> is all on the stack and no garbage collection is needed for that data.
The stack has a finite amount of memory.
This means that for large strings, the above code will result in a `StackOverflowException` being thrown.
So what is the limit for the amount of memory we can allocate?
Well, this depends on how memory has already been allocated on the stack.
That said, a small test program successfully stack-allocated memory for 750_000 characters, so you might be fine.
StringBuilder
StringBuilder
module ReverseString
open System.Text
let reverse (input: string) =
let chars = StringBuilder()
for char in Seq.rev input do
chars.Append(char) |> ignore
chars.ToString()
Strings can also be created using the StringBuilder class.
The purpose of this class is to efficiently and incrementally build a string.
A `StringBuilder` is often overkill when used to create short strings, but can be very useful to create larger strings.
The first step is to create a StringBuilder.
We then use a for-loop to walk through the string’s characters in reverse order via the Seq.rev function, appending them to the StringBuilder via its Append() method.
Finally, we return the reversed string by calling the ToString() method on the StringBuilder instance.
Source: Exercism fsharp/reverse-string