CODEWITHSUNDEEP
f#
Jamie Dixon
Jamie Dixon

Reputation: 4282

F# Array Of String: concatenating values

I have an array like this:

let items = ["A";"B";"C";"D"]

I want to transform it into an array like this:

let result = ["AB";"AC";"AD";"BC";"BD";"CD"]

I can't find anything in the language spec that does this - though I might be searching incorrectly. I thought of Seq.Fold like this:

let result = items |> Seq.fold(fun acc x -> acc+x) ""

but I am getting "ABCD"

Does anyone know how to do this? Will a modified CartesianProduct work?

Thanks in advance

Upvotes: 1

Views: 788

Answers (6)

Michael Beidler
Michael Beidler

Reputation: 118

This is an apt motivating example for implementing a List monad in F#. Using F# computation expressions, we get:

type ListMonadBuilder() = 
    member b.Bind(xs, f) = List.collect f xs
    member b.Delay(f)    = fun () -> f()
    member b.Let(x, f)   = f x
    member b.Return(x)   = [x]
    member b.Zero()      = []

let listM = new ListMonadBuilder()

Now, to solve the original problem we simply use our List monad.

let run = listM {
    let! x = ['A' .. 'D']
    let! y = List.tail [ x  .. 'D']
    return string x + string y
}

run();; in F# Interactive will return the desired result.

For another example of using the List monad, we can get the Pythagorean triples <= n.

let pythagoreanTriples n = listM {
    let! c = [1 .. n]
    let! b = [1 .. c]
    let! a = [1 .. b]
    if a*a + b*b = c*c then return (a, b, c)
}

Running pythagoreanTriples 10 ();; in F# interactive returns:

val it : (int * int * int) list = [(3, 4, 5); (6, 8, 10)]

Upvotes: 1

desco
desco

Reputation: 16782

let items = ["A";"B";"C";"D"]
let rec produce (l: string list) =
    match l with
    // if current list is empty or contains one element - return empty list
    | [] | [_] -> [] 
    // if current list is not empty - match x to head and xs to tail
    | x::xs -> 
        [
            // (1) 
            // iterate over the tail, return string concatenation of head and every item in tail 
            for c in xs -> x + c 
            // apply produce to tail, concat return values
            yield! produce xs
        ]

1st iteration: l = [A, B, C, D] - is not empty, in second match case we'll have x = A, xs = [B, C, D]. 'for' part of the list expression will yield [AB, AC, AD] and result of applying produce to xs.

2nd iteration:l = [B, C, D] is not empty so second match case we'll have x = B, xs = [C, D]. 'for' part of the list expression will yield [BC, BD] and result of applying produce to xs.

3rd iteration:l = [C, D] is not empty in second match case we'll have x = C, xs = [D]. 'for' part of the list expression will yield [CD] and result of applying produce to xs.

4th iteration:l = [D] contains one element -> return empty list.

Final result will be concatenation of [AB, AC, AD] ++ [BC, BD] ++ [CD]

Upvotes: 1

S&#248;ren Debois
S&#248;ren Debois

Reputation: 5688

I'd do it like this:

let rec loop = function 
    [] -> []
  | x :: xs -> List.map ((^) x) xs @ loop xs

This has the advantage of not building every pair of elements from the list only to discard half. (I'll leave getting rid of the append as an exercise :-)

For me, it is a bit easier to tell what's going on here compared some of the other proposed solutions. For this kind of problem, where to process an element x you need also access to the rest of the list xs, standard combinators won't always make solutions clearer.

Upvotes: 1

Lee
Lee

Reputation: 144126

You could create a function to create a list of all head/tail pairs in a list:

let rec dec = function
| [] -> []
| (x::xs) -> (x, xs) :: dec xs

or a tail-recursive version:

let dec l =
    let rec aux acc = function
        | [] -> acc
        | (x::xs) -> aux ((x, xs)::acc) xs

    aux [] l |> List.rev

you can then use this function to create your list:

let strs (l: string list) = l |> dec |> List.collect (fun (h, t) -> List.map ((+)h) t)

Upvotes: 1

Jack P.
Jack P.

Reputation: 11525

What you have there are lists, not arrays -- lists use the [...] syntax, arrays use the [|...|] syntax.

That said, here's a simple implementation:

let listProduct (items : string list) =
    items
    |> List.collect (fun x ->
        items
        |> List.choose (fun y ->
            if x < y then Some (x + y)
            else None))

If you put it into F# interactive:

> let items = ["A"; "B"; "C"; "D"];;

val items : string list = ["A"; "B"; "C"; "D"]

> items |> listProduct |> Seq.toList;;
val it : string list = ["AB"; "AC"; "AD"; "BC"; "BD"; "CD"]

Upvotes: 3

Mark Seemann
Mark Seemann

Reputation: 233135

Something like this should do it:

items
|> List.map (fun x -> items |> List.map (fun y -> (x, y)))
|> List.concat
|> List.filter (fun (x, y) -> x < y)
|> List.map (fun (x, y) -> x + y)
|> List.sort

I don't know if it's efficient for large lists, but it does produce this output:

["AB"; "AC"; "AD"; "BC"; "BD"; "CD"]

Breakdown

The first step produces a list of list of tuples, by mapping items twice:

[[("A", "A"); ("A", "B"); ("A", "C"); ("A", "D")];
 [("B", "A"); ("B", "B"); ("B", "C"); ("B", "D")];
 [("C", "A"); ("C", "B"); ("C", "C"); ("C", "D")];
 [("D", "A"); ("D", "B"); ("D", "C"); ("D", "D")]]

Second, List.concat turns the list of list into a single list:

[("A", "A"); ("A", "B"); ("A", "C"); ("A", "D"); ("B", "A"); ("B", "B");
 ("B", "C"); ("B", "D"); ("C", "A"); ("C", "B"); ("C", "C"); ("C", "D");
 ("D", "A"); ("D", "B"); ("D", "C"); ("D", "D")]

Third, List.filter removes the tuples where the first element is equal to or larger than the second element:

[("A", "B"); ("A", "C"); ("A", "D"); ("B", "C"); ("B", "D"); ("C", "D")]

Fourth, List.map produces a list of concatenated strings:

["AB"; "AC"; "AD"; "BC"; "BD"; "CD"]

Finally, List.sort sorts the list, although in this case it's not necessary, as the list already has the correct order.

You might also consider using Seq.distinct to remove duplicates, if there are any.

Upvotes: 2

Related Questions