Skip to content

Instantly share code, notes, and snippets.

@manofstick
Created June 21, 2023 05:01
Show Gist options
  • Save manofstick/365931e24a5d3a1ef9f07fdda3020ca7 to your computer and use it in GitHub Desktop.
Save manofstick/365931e24a5d3a1ef9f07fdda3020ca7 to your computer and use it in GitHub Desktop.
FSharp filter
[<System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.NoInlining)>]
let invalidStateOfEmptyList () = raise (System.InvalidProgramException "list can not be empty")
/// optimized filter if filtered items are all at the end of the list then that list is returned
/// the function entryToFilterToFreshConsTail was the original version of filter, and is used
/// in the case of there being multiple segments in the data
let filter predicate originalList =
let rec entryToFilterToFreshConsTail lst =
match lst with
| [] -> []
| hd :: tl when predicate hd ->
match tl with
| [] -> lst
| _ ->
let cons = freshConsNoTail hd
filterToFreshConsTail cons predicate tl
cons
| _ :: tl -> entryToFilterToFreshConsTail tl
let rec prependFirstSegmentItems exclusiveFirstSegmentEnd firstSegmentPtr newListWithNoTail =
match firstSegmentPtr with
| [] -> invalidStateOfEmptyList ()
| _ when obj.ReferenceEquals (firstSegmentPtr, exclusiveFirstSegmentEnd) -> newListWithNoTail
| hd :: tl ->
let nextElement = freshConsNoTail hd
setFreshConsTail newListWithNoTail nextElement
prependFirstSegmentItems exclusiveFirstSegmentEnd tl nextElement
let handleMultipleSegements inclusiveFirstSegementStart exclusiveFirstSegmentEnd tl =
let filteredTail = entryToFilterToFreshConsTail tl
match inclusiveFirstSegementStart with
| [] -> invalidStateOfEmptyList ()
| firstElement::remainingFirstSegmentElements ->
let firstItem = freshConsNoTail firstElement
let lastItemWithNoTail = prependFirstSegmentItems exclusiveFirstSegmentEnd remainingFirstSegmentElements firstItem
setFreshConsTail lastItemWithNoTail filteredTail
firstItem
let rec inFirstSegment startFirstSegment current =
match current with
| [] -> startFirstSegment
| hd::tl when predicate hd -> inFirstSegment startFirstSegment tl
| _::tl -> handleMultipleSegements startFirstSegment current tl
let rec preFirstSegement lst =
match lst with
| [] -> []
| hd::tl when predicate hd -> inFirstSegment lst tl
| _::tl -> preFirstSegement tl
preFirstSegement originalList
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment