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.

Copy Source
Copy Link
Tools:
 1: /// Given two sequences and a comparator function, find the pairs of items for 
 2: /// which the comparator returns true
 3: let findPairs compare seqT seqU =
 4:     seq {
 5:             for t in seqT do
 6:                 for u in seqU do
 7:                     if (compare t u) then
 8:                         yield (t, u)
 9:     }
10: 
11: /// Given two sequences and a comparator function, find the first pair of items 
12: /// for which the comparator returns true
13: let tryFindFirstPair compare seqT seqU =
14:     let matches = findPairs compare seqT seqU
15:     if not (Seq.isEmpty matches) then
16:         Some(Seq.nth 0 matches)
17:     else
18:         None
19: 
20: //// A quick demo to generate lists of rhyming words:
21: 
22: /// Reverse a string (from TomasP):
23: let reverse (s:string) =
24:   let rec reverseAux idx acc =
25:     if (idx = s.Length) then acc
26:     else reverseAux (idx+1) ((s.[idx])::acc)
27:   new string(Array.ofList (reverseAux 0 []))
28: 
29: /// A crude way to work out the last syllable for a word:
30: let lastSyllable word =
31:     let vowels = [|'a';'e';'i';'o';'u';'y'|]
32:     let wordRev = reverse word
33:     let vowelPos = wordRev.IndexOfAny(vowels, 1)
34:     let lastSylRev = wordRev.Substring(0, vowelPos+1)
35:     reverse lastSylRev
36: 
37: /// Return true when words might rhyme based on their final syllables being 
38: /// the same
39: let mightRhyme wordA wordB =
40:     (wordA <> wordB) && (lastSyllable wordA = lastSyllable wordB)
41: 
42: /// Two steams of words, some of which might rhyme
43: let words1 = ["orange"; "purple"; "hubble"; "indicative"; "mandatory"]
44: let words2 = ["hurple"; "rhubarb"; "tory"; "bubble"]
45: 
46: /// Find the rhymes
47: findPairs mightRhyme words1 words2
48: 
49: // Output: seq [("purple", "hurple"); ("hubble", "bubble"); ("mandatory", "tory")]
50: 
51: /// Find the rhymes in a single stream of words:
52: let wordsAll = ["orange"; "purple"; "hubble"; "indicative"; "mandatory"; "hurple"; "rhubarb"; "tory"; "bubble"]
53: findPairs mightRhyme wordsAll wordsAll
54: 
55: // Output: seq
56: //    [("purple", "hurple"); ("hubble", "bubble"); ("mandatory", "tory");
57: //     ("hurple", "purple"); ...]
val findPairs : ('a -> 'b -> bool) -> seq<'a> -> seq<'b> -> seq<'a * 'b>

Full name: Snippet.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>

  type: seq<'a>
  inherits: System.Collections.IEnumerable
val seqU : seq<'b>

  type: seq<'b>
  inherits: System.Collections.IEnumerable
Multiple items
val seq : 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<_>

  type: seq<'T>
  inherits: System.Collections.IEnumerable
val t : 'a
val u : 'b
val tryFindFirstPair : ('a -> 'b -> bool) -> seq<'a> -> seq<'b> -> ('a * 'b) option

Full name: Snippet.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>

  type: seq<'a * 'b>
  inherits: System.Collections.IEnumerable
val not : bool -> bool

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

from Microsoft.FSharp.Collections
val isEmpty : seq<'T> -> bool

Full name: Microsoft.FSharp.Collections.Seq.isEmpty
union case Option.Some: 'T -> Option<'T>
val nth : int -> seq<'T> -> 'T

Full name: Microsoft.FSharp.Collections.Seq.nth
union case Option.None: Option<'T>
val reverse : string -> string

Full name: Snippet.reverse

Reverse a string (from TomasP):
val s : string

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>
Multiple items
val string : 'T -> string

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

--------------------

type string = System.String

Full name: Microsoft.FSharp.Core.string

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>
val reverseAux : (int -> char list -> char list)
val idx : int

  type: int
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<int>
  implements: System.IEquatable<int>
  inherits: System.ValueType
val acc : char list

  type: char list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<char>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<char>
  implements: System.Collections.IEnumerable
property System.String.Length: int
module Array

from Microsoft.FSharp.Collections
val ofList : 'T list -> 'T []

Full name: Microsoft.FSharp.Collections.Array.ofList
val lastSyllable : string -> string

Full name: Snippet.lastSyllable

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

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>
val vowels : char []

  type: char []
  implements: System.ICloneable
  implements: System.Collections.IList
  implements: System.Collections.ICollection
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.IStructuralEquatable
  implements: System.Collections.Generic.IList<char>
  implements: System.Collections.Generic.ICollection<char>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  inherits: System.Array
val wordRev : string

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>
val vowelPos : int

  type: int
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<int>
  implements: System.IEquatable<int>
  inherits: System.ValueType
Multiple overloads
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

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>
Multiple overloads
System.String.Substring(startIndex: int) : string
System.String.Substring(startIndex: int, length: int) : string
val mightRhyme : string -> string -> bool

Full name: Snippet.mightRhyme

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

val wordA : string

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>
val wordB : string

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>
val words1 : string list

Full name: Snippet.words1

  type: string list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<string>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<string>
  implements: System.Collections.IEnumerable


Two steams of words, some of which might rhyme
val words2 : string list

Full name: Snippet.words2

  type: string list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<string>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<string>
  implements: System.Collections.IEnumerable
val wordsAll : string list

Full name: Snippet.wordsAll

  type: string list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<string>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<string>
  implements: System.Collections.IEnumerable


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

More information

Link: http://fssnip.net/75
Posted: 3 years ago
Author: Kit Eason (website)
Tags: learning F#, sequences