1 people like it.
Like the snippet!

Finding matching pairs in two sequences

Here's a function which takes a comparator function and two sequences, and returns tuples consisting of an item from each sequence, where the comparator function returns true for those two items. This is a small part of my wider project to generate guitar chord shapes. One of the requirements there is to take a list of 'wanted' notes for a chord, and a list of 'available' notes within a range of frets and to combine them into an actual set of frettings. That's what led to tryFindFirstPair and hence to findPairs.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 
56: 
57:

/// Given a two sequences and a comparator function, find the pairs of items for 
/// which the comparator returns true
let findPairs compare seqT seqU =
    seq {
            for t in seqT do
                for u in seqU do
                    if (compare t u) then
                        yield (t, u)
    }

/// Given a two sequences and a comparator function, find the first pair of items 
/// for which the comparator returns true
let tryFindFirstPair compare seqT seqU =
    let matches = findPairs compare seqT seqU
    if not (Seq.isEmpty matches) then
        Some(Seq.nth 0 matches)
    else
        None

//// A quick demo to generate lists of rhyming words:

/// Reverse a string (from TomasP):
let reverse (s:string) =
  let rec reverseAux idx acc =
    if (idx = s.Length) then acc
    else reverseAux (idx+1) ((s.[idx])::acc)
  new string(Array.ofList (reverseAux 0 []))

/// A crude way to work out the last syllable for a word:
let lastSyllable word =
    let vowels = [|'a';'e';'i';'o';'u';'y'|]
    let wordRev = reverse word
    let vowelPos = wordRev.IndexOfAny(vowels, 1)
    let lastSylRev = wordRev.Substring(0, vowelPos+1)
    reverse lastSylRev

/// Return true when words might rhyme based on their final syllables being 
/// the same
let mightRhyme wordA wordB =
    (wordA <> wordB) && (lastSyllable wordA = lastSyllable wordB)

/// Two steams of words, some of which might rhyme
let words1 = ["orange"; "purple"; "hubble"; "indicative"; "mandatory"]
let words2 = ["hurple"; "rhubarb"; "tory"; "bubble"]

/// Find the rhymes
findPairs mightRhyme words1 words2

// Output: seq [("purple", "hurple"); ("hubble", "bubble"); ("mandatory", "tory")]

/// Find the rhymes in a single stream of words:
let wordsAll = ["orange"; "purple"; "hubble"; "indicative"; "mandatory"; "hurple"; "rhubarb"; "tory"; "bubble"]
findPairs mightRhyme wordsAll wordsAll

// Output: seq
//    [("purple", "hurple"); ("hubble", "bubble"); ("mandatory", "tory");
//     ("hurple", "purple"); ...]

val findPairs : compare:('a -> 'b -> bool) -> seqT:seq<'a> -> seqU:seq<'b> -> seq<'a * 'b>

Full name: Script.findPairs

Given a two sequences and a comparator function, find the pairs of items for
which the comparator returns true

val compare : ('a -> 'b -> bool)

val seqT : seq<'a>

val seqU : seq<'b>

Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>

val t : 'a

val u : 'b

val tryFindFirstPair : compare:('a -> 'b -> bool) -> seqT:seq<'a> -> seqU:seq<'b> -> ('a * 'b) option

Full name: Script.tryFindFirstPair

Given a two sequences and a comparator function, find the first pair of items
for which the comparator returns true

val matches : seq<'a * 'b>

val not : value:bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not

module Seq

from Microsoft.FSharp.Collections

val isEmpty : source:seq<'T> -> bool

Full name: Microsoft.FSharp.Collections.Seq.isEmpty

union case Option.Some: Value: 'T -> Option<'T>

val nth : index:int -> source:seq<'T> -> 'T

Full name: Microsoft.FSharp.Collections.Seq.nth

union case Option.None: Option<'T>

val reverse : s:string -> string

Full name: Script.reverse

Reverse a string (from TomasP):

val s : string

Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

--------------------
type string = System.String

Full name: Microsoft.FSharp.Core.string

val reverseAux : (int -> char list -> char list)

val idx : int

val acc : char list

property System.String.Length: int

module Array

from Microsoft.FSharp.Collections

val ofList : list:'T list -> 'T []

Full name: Microsoft.FSharp.Collections.Array.ofList

val lastSyllable : word:string -> string

Full name: Script.lastSyllable

A crude way to work out the last syllable for a word:

val word : string

val vowels : char []

val wordRev : string

val vowelPos : int

System.String.IndexOfAny(anyOf: char []) : int
System.String.IndexOfAny(anyOf: char [], startIndex: int) : int
System.String.IndexOfAny(anyOf: char [], startIndex: int, count: int) : int

val lastSylRev : string

System.String.Substring(startIndex: int) : string
System.String.Substring(startIndex: int, length: int) : string

val mightRhyme : wordA:string -> wordB:string -> bool

Full name: Script.mightRhyme

Return true when words might rhyme based on their final syllables being
the same

val wordA : string

val wordB : string

val words1 : string list

Full name: Script.words1

Two steams of words, some of which might rhyme

val words2 : string list

Full name: Script.words2

val wordsAll : string list

Full name: Script.wordsAll

Find the rhymes
Find the rhymes in a single stream of words:

Next Version Raw view Test code New version

More information

Link:	http://fssnip.net/75
Posted:	13 years ago
Author:	Kit Eason
Tags:	learning f# , sequences