1

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

6 Answers 6

3

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"]
2
  • This only works if your inputs are sorted right? If the user has ["d"; "b"; "a"] then it won't work
    – devshorts
    Mar 8, 2014 at 16:42
  • @devshorts That's correct. The question doesn't state the input would be sorted, but that seems to be the case given the example input and output data. If not, you'd need to sort the input (e.g., with List.sort) first.
    – Jack P.
    Mar 8, 2014 at 18:24
2

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.

3
  • Thanks guys. I guess there is nothing out of the box in the F# spec that does this. Drat! I prefer Mark's syntax to Jack's because I really try and avoid using "if...else" when I write F#. Both will work - hope this helps someone else... Mar 8, 2014 at 14:55
  • @JamieDixon One thing to consider -- if your lists or arrays are relatively large, avoiding the "if ... else" syntax is going to cost you a lot of performance. Mark's solution produces the result you want, but it also has a significant amount of overhead (both CPU and memory/GC) since it creates a new list between each step. The difference won't be noticeable for small lists, but it will be for larger lists.
    – Jack P.
    Mar 8, 2014 at 15:15
  • Well, I did say that "I don't know if it's efficient for large lists", but the part about creating a new list every time can be easily addressed. You can replace all the 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. Mar 8, 2014 at 15:37
1

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)
0
1

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.

1
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]

0
1

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)]
1
  • You can use List.collect instead of concatMap
    – Gus
    May 15, 2014 at 18:34

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.