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
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"]
List.sort) first.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.
List functions with Seq functions in the above code, and it will still work... e.g. replace List.map with Seq.map, List.concat with Seq.concat, etc. I just used functions from the List module because it's easier to look at results in F# Interactive, and because the OP asked for a list.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)
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.
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]
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)]
