1 people like it.

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 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 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 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 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:

More information

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