CODEWITHSUNDEEP
f#fold
Balinth
Balinth

Reputation: 568

F# folding gracefully without the first or last element?

Say you have a list of strings: [ "a"; "b"; "c" ] and you want to transform it to a single string like so: "a,b,c" notice that the last comma is missing. I find this case comes up again and again for me, think of all the programming languages that do not allow the trailing comma to be there, and you are building some kind of code generator. I usually end up with something like:

let listOfThings = ["a";"b";"c"]
let folded =
    listOfThings
    |> List.map (fun i -> i + ",")
    |> List.fold (+) ""
    |> (fun s -> s.Substring(0, s.Length - 1))

I feel like there is some fold like function already because this seems such a basic use case, and I just can't figure out what would be it's name, or by what name to search for it.

Upvotes: 2

Views: 543

Answers (3)

CaringDev
CaringDev

Reputation: 8551

Indeed, there is a built in function that does this:

let s = [ "a"; "b"; "c" ]
String.concat ", " s // "a, b, c"

Upvotes: 0

Asti
Asti

Reputation: 12667

A fold applies your folding function recursively over all values of the list, starting with an initial state, which you don't particularly want in this case.

It's simpler to use a reduce which uses the list's head as its starting state:

listOfThings |> List.reduce (fun sum cur -> sum + "," + cur) // "a,b,c"

A minor drawback is that since it uses the list head, calling reduce with an empty list would fail. You can mitigate that with a check for an empty list.

Without any built-ins, as you have described, we skip the addition of the trailing comma for the last element:

let rec join = function
| []    -> ""
| [x]   -> x
| x::xs -> x + ","  + join xs

["a"; "b"; "c"] |> join // a,b,c

However, the most efficient method would be to use String.Join which internally uses a StringBuilder, while reduce allocates a new string for every call:

String.Join(",", listOfThings) // "a,b,c"

Upvotes: 5

kaefer
kaefer

Reputation: 5741

A reduction applied to the elements of a list is necessarily of the same type as these are. In contrast, the accumulator (also called state) of a fold can be of a different type, which is more versatile. The signatures make it apparent:

val reduce: ('a -> 'a -> 'a) -> 'a list -> 'a
val fold: ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

A possible approach might consist in provision of a different folding function for the first element of the list (or for the last, in the case of foldBack). Here it is also prudent to check for an empty list, as it is with reduce.

let fold1 folderN folder0 state = function
| [] -> state
| x::xs -> List.fold folderN (folder0 state x) xs
// val fold1 :
//   folderN:('a -> 'b -> 'a) ->
//     folder0:('a -> 'b -> 'a) -> state:'a -> _arg1:'b list -> 'a

Now we can fold into a list, or even use a StringBuilder:

([], ["a";"b";"c"])
||> fold1 
    (fun s t -> t::", "::s)
    (fun s t -> t::s)
|> List.rev
// val it : string list = ["a"; ", "; "b"; ", "; "c"]

(System.Text.StringBuilder(), ["a";"b";"c"])
||> fold1 
    (fun s t -> s.Append(", ").Append t)
    (fun s t -> s.Append t) 
|> string
// val it : string = "a, b, c"

Upvotes: 3

Related Questions