Created
May 22, 2014 07:56
-
-
Save ninegrid/972aa47c91ec8be1b749 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Learn more about F# at http://fsharp.net | |
namespace BasicConcepts | |
module Algorithms = | |
let ``1.1E`` (m : uint32) (n : uint32) = | |
let rec aux m n l = | |
let r = m % n | |
if r <> 0u then aux n r (r :: l) else l | |
aux m n [] |> Seq.head | |
open Algorithms | |
//module Tests = | |
// do ``1.1E`` 119u 544u |> ignore | |
module Excersizes = | |
let ``1.1_1[10]`` a b c d = | |
let mutable a' = a | |
let mutable b' = b | |
let mutable c' = c | |
let mutable d' = d | |
let mutable t = a | |
a' <- b | |
b' <- c | |
c' <- d | |
d' <- t | |
(a,b,c,d) | |
let ``1.1_2[15]`` (m : uint32) (n : uint32) = | |
(m % n, n % m) | |
let ``1.1_3[20]`` m n = | |
let ``1.1F`` (m : uint32) (n : uint32) = | |
let rec aux m n l = | |
if m < n then aux n m l | |
else | |
let r = m % n | |
if r <> 0u then aux n r (r :: l) else l | |
aux m n [] |> Seq.head in | |
``1.1F`` m n | |
let ``1.1_4[16]`` = ``1.1_3[20]`` 2166u 6099u | |
let ``1.1_5[12]`` = () (* regarding the algorithm for reading the book and not applicable to code *) | |
let ``1.1_6[20]`` = | |
let commonDivisors (m : uint32) (n : uint32) = | |
let rec aux m n l = | |
let r = m % n | |
let l' = r :: l | |
if r <> 0u then aux n r l' else l | |
aux m n [] | |
seq { for i in 1u..100000u do yield! [commonDivisors i 5u] } | |
|> Seq.map (fun xs -> float (Seq.length xs) + 1.) | |
|> Seq.average | |
let ``1.1_7[M21]`` = | |
let commonDivisors (m : uint32) (n : uint32) = | |
let rec aux m n l = | |
let r = m % n | |
let l' = r :: l | |
if r <> 0u then aux n r l' else l | |
aux m n [] | |
seq { for i in 1u..100000u do yield! [commonDivisors 5u i] } | |
|> Seq.map (fun xs -> float (Seq.length xs) + 1.) | |
|> Seq.average | |
let ``1.1_8[M25]`` = () (* hard *) | |
let ``1.1_9[M30]`` = () (* hard *) | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
namespace BasicConcepts | |
module Algorithms = | |
/// <summary>Euclid's Algorithm</summary> | |
/// <remarks> | |
/// Given two positive integers m and n, find their greatest common divisor, that is, the largest positive | |
/// integer that evenly divides both m and n. | |
/// </remarks> | |
/// <typeparam name="m"></typeparam> | |
/// <typeparam name="n"></typeparam> | |
/// <returns>uint32</returns> | |
val ``1.1E`` : uint32 -> uint32 -> uint32 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| |
// Learn more about F# at http://fsharp.net | |
namespace BasicConcepts | |
module Algorithms = | |
let ``1.1E`` (m : uint32) (n : uint32) = | |
let rec aux m n l = | |
let r = m % n | |
if r <> 0u then aux n r (r :: l) else l | |
aux m n [] |> Seq.head | |
open Algorithms | |
//module Tests = | |
// do ``1.1E`` 119u 544u |> ignore | |
module Excersizes = | |
let ``1.1_1[10]`` a b c d = | |
let mutable a' = a | |
let mutable b' = b | |
let mutable c' = c | |
let mutable d' = d | |
let mutable t = a | |
a' <- b | |
b' <- c | |
c' <- d | |
d' <- t | |
(a,b,c,d) | |
let ``1.1_2[15]`` (m : uint32) (n : uint32) = | |
(m % n, n % m) | |
let ``1.1_3[20]`` m n = | |
let ``1.1F`` (m : uint32) (n : uint32) = | |
let rec aux m n l = | |
if m < n then aux n m l | |
else | |
let r = m % n | |
if r <> 0u then aux n r (r :: l) else l | |
aux m n [] |> Seq.head in | |
``1.1F`` m n | |
let ``1.1_4[16]`` = ``1.1_3[20]`` 2166u 6099u | |
let ``1.1_5[12]`` = () (* regarding the algorithm for reading the book and not applicable to code *) | |
let ``1.1_6[20]`` = | |
let commonDivisors (m : uint32) (n : uint32) = | |
let rec aux m n l = | |
let r = m % n | |
let l' = r :: l | |
if r <> 0u then aux n r l' else l | |
aux m n [] | |
seq { for i in 1u..100000u do yield! [commonDivisors i 5u] } | |
|> Seq.map (fun xs -> float (Seq.length xs) + 1.) | |
|> Seq.average | |
let ``1.1_7[M21]`` = | |
let commonDivisors (m : uint32) (n : uint32) = | |
let rec aux m n l = | |
let r = m % n | |
let l' = r :: l | |
if r <> 0u then aux n r l' else l | |
aux m n [] | |
seq { for i in 1u..100000u do yield! [commonDivisors 5u i] } | |
|> Seq.map (fun xs -> float (Seq.length xs) + 1.) | |
|> Seq.average | |
let ``1.1_8[M25]`` = () (* hard *) | |
let ``1.1_9[M30]`` = () (* hard *) | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
|
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
namespace BasicConcepts | |
module MathematicalPreliminaries = | |
let ``1.2.1I`` (P : int -> bool) (n : int) = | |
seq [ 1 .. n + 1 ] |> Seq.tryPick (fun k -> if P k then None else Some(k)) | |
let ``1.2.1E`` (m : int) (n : int) = | |
let rec aux a' a b' b c d m n = | |
let q = c / d | |
let r = c % d | |
if r = 0 then printfn "%A" (a',a,b',b,c,d,q,r); (a',a,b',b,c,d,q,r) | |
else | |
printfn "%A" (a',a,b',b,c,d,q,r) | |
aux a (a'-(q*a)) b (b'-(q*b)) d r m n | |
aux 1 0 0 1 m n m n | |
open MathematicalPreliminaries | |
module Tests = | |
let induct = ``1.2.1I`` | |
let ``1.2.1.Eq. (2)`` n = | |
let x = float n | |
if Seq.reduce (+) [1. .. 2. .. (2.*x) - 1.] = x ** 2. then true else false | |
let t0 = induct ``1.2.1.Eq. (2)`` 10 | |
let fibs = Seq.unfold (fun (n0, n1) -> Some(n0, (n1, n0+n1))) (0I,1I) | |
let phi = (1. + (sqrt 5.)) / 2. | |
let ``1.2.1.Eq. (3)`` n = | |
if (float (Seq.nth n fibs) <= (phi ** (float (n - 1)))) then true else false | |
let t1 = induct ``1.2.1.Eq. (3)`` 10 | |
(* learn to do ``1.2.1.Eq (4)`` *) | |
let ``1.2.1.Eq. (5)`` = (1. + phi = phi ** 2.) | |
let t2 = ``1.2.1E`` 1000000 10000000 | |
let ``1.2.1.Eq (6)`` = | |
let m = 1769 | |
let n = 551 | |
match ``1.2.1E`` m n with | |
| (a',a,b',b,c,d,q,r) -> if (((a' * m) + (b' * n) = c) | |
&& ((a * m) + (b * n) = d)) then true else false | |
module Excersizes = | |
let ``1.2.1.Ex.1[05]`` = () | |
let ``1.2.1.Ex.2[15]`` = () | |
let ``1.2.1.Ex.3[18]`` = () | |
let ``1.2.1.Ex.4[20]`` = () | |
let ``1.2.1.Ex.5[21]`` = () | |
let ``1.2.1.Ex.6[20]`` = () | |
let ``1.2.1.Ex.7[23]`` = () | |
let ``1.2.1.Ex.8[25]`` = () | |
let ``1.2.1.Ex.9[20]`` = () | |
let ``1.2.1.Ex.10[M22]`` = () | |
let ``1.2.1.Ex.11[M30]`` = () | |
let ``1.2.1.Ex.12[M25]`` = () | |
let ``1.2.1.Ex.13[M23]`` = () | |
let ``1.2.1.Ex.14[50]`` = () | |
let ``1.2.1.Ex.15[HM28]`` = () | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
namespace BasicConcepts | |
module MathematicalPreliminaries = | |
val ``1.2.1I`` : (int -> bool) -> int -> int option | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
namespace BasicConcepts | |
module MathematicalPreliminaries = | |
let ``1.2.1I`` (P : int -> bool) (n : int) = | |
seq [ 1 .. n + 1 ] |> Seq.tryPick (fun k -> if P k then None else Some(k)) | |
let ``1.2.1E`` (m : int) (n : int) = | |
let rec aux a' a b' b c d m n = | |
let q = c / d | |
let r = c % d | |
if r = 0 then printfn "%A" (a',a,b',b,c,d,q,r); (a',a,b',b,c,d,q,r) | |
else | |
printfn "%A" (a',a,b',b,c,d,q,r) | |
aux a (a'-(q*a)) b (b'-(q*b)) d r m n | |
aux 1 0 0 1 m n m n | |
open MathematicalPreliminaries | |
module Tests = | |
let induct = ``1.2.1I`` | |
let ``1.2.1.Eq. (2)`` n = | |
let x = float n | |
if Seq.reduce (+) [1. .. 2. .. (2.*x) - 1.] = x ** 2. then true else false | |
let t0 = induct ``1.2.1.Eq. (2)`` 10 | |
let fibs = Seq.unfold (fun (n0, n1) -> Some(n0, (n1, n0+n1))) (0I,1I) | |
let phi = (1. + (sqrt 5.)) / 2. | |
let ``1.2.1.Eq. (3)`` n = | |
if (float (Seq.nth n fibs) <= (phi ** (float (n - 1)))) then true else false | |
let t1 = induct ``1.2.1.Eq. (3)`` 10 | |
(* learn to do ``1.2.1.Eq (4)`` *) | |
let ``1.2.1.Eq. (5)`` = (1. + phi = phi ** 2.) | |
let t2 = ``1.2.1E`` 1000000 10000000 | |
let ``1.2.1.Eq (6)`` = | |
let m = 1769 | |
let n = 551 | |
match ``1.2.1E`` m n with | |
| (a',a,b',b,c,d,q,r) -> if (((a' * m) + (b' * n) = c) | |
&& ((a * m) + (b * n) = d)) then true else false | |
module Excersizes = | |
let ``1.2.1.Ex.1[05]`` = () | |
let ``1.2.1.Ex.2[15]`` = () | |
let ``1.2.1.Ex.3[18]`` = () | |
let ``1.2.1.Ex.4[20]`` = () | |
let ``1.2.1.Ex.5[21]`` = () | |
let ``1.2.1.Ex.6[20]`` = () | |
let ``1.2.1.Ex.7[23]`` = () | |
let ``1.2.1.Ex.8[25]`` = () | |
let ``1.2.1.Ex.9[20]`` = () | |
let ``1.2.1.Ex.10[M22]`` = () | |
let ``1.2.1.Ex.11[M30]`` = () | |
let ``1.2.1.Ex.12[M25]`` = () | |
let ``1.2.1.Ex.13[M23]`` = () | |
let ``1.2.1.Ex.14[50]`` = () | |
let ``1.2.1.Ex.15[HM28]`` = () | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| |
#r "FSharp.PowerPack.dll" | |
module LazyListIntegerPartitionDelayed = | |
exception Subscript | |
type Partition = int LazyList | |
type CompressedPartition = int * Partition | |
(* val expand : CompressedPartition -> Partition *) | |
let rec expand (p : CompressedPartition) = | |
match p with | |
| 0,p -> p | |
| n,p -> (expand ((n-1), LazyList.consDelayed 1 (fun () -> p))) | |
(* val pack : int -> CompressedPartition -> CompressedPartition *) | |
let rec pack (n : int) (cp : CompressedPartition) = | |
match n with | |
| 1 -> cp | |
| k -> if k > (fst cp) then pack (k-1) (cp) | |
else pack k (((fst cp) - k), LazyList.consDelayed k (fun () -> (snd cp))) | |
(* val nextpartition : CompressedPartition -> CompressedPartition *) | |
let nextPartition (cp : CompressedPartition) = | |
match cp with | |
| k,LazyList.Cons(x,xs) -> pack (x-1) ((k+x),xs) | |
| k,LazyList.Nil -> raise Subscript | |
let rev (xs : LazyList< 'a >) : LazyList< 'a > = | |
let rec loop xs ys = | |
match xs with | |
LazyList.Nil -> ys | |
| LazyList.Cons(x, xs) -> loop xs (LazyList.consDelayed x (fun () -> ys)) | |
loop xs LazyList.empty | |
(* val generatePs : CompressedPartition -> Partition list *) | |
let generatePartitions (cp : CompressedPartition) = | |
let rec loop (cp : CompressedPartition) rs = | |
match cp with | |
| n,LazyList.Nil -> (LazyList.cons (rev (expand cp)) rs) | |
| n,LazyList.Cons(x,xs) -> loop (nextPartition cp) (LazyList.consDelayed (rev (expand cp)) (fun () -> rs)) | |
loop cp LazyList.empty | |
(* val part : int -> Partition list *) | |
let rec part n (lexicographic : bool) = | |
match lexicographic with | |
| false -> part n (true) |> rev | |
| true -> match n with | |
| n when n < 1 -> raise Subscript | |
| n when n = 1 -> LazyList.consDelayed (LazyList.ofList [1]) (fun () -> (LazyList.empty)) | |
| _ -> generatePartitions (0,(LazyList.ofList [n])) | |
open LazyListIntegerPartitionDelayed | |
#time | |
part 60 true | |
(* Notes for making it tail-recursive. *) | |
(* naive implementation not tail recursive *) | |
let rec count n = | |
match n with | |
0 -> [] | |
| n -> n :: count (n - 1) | |
(* ^ | |
|.... the cons operator is in the tail position | |
as such, it is evaluated last, so this drags | |
the stack through all recursive calls *) | |
(* apply continuation passing style with parameterized function *) | |
let count' n = | |
let rec count n ret = | |
match n with | |
0 -> ret [] (* v------ this is continuation passing style *) | |
| n -> count (n - 1) (fun cs -> n :: cs) | |
(* ^ | |
|... the recursive call is now in tail position *) | |
count n (fun cs -> cs) | |
(* refactor the parameterized function into a specialized representation | |
this is an optimization of the second example. if you have something | |
like the first example and you can't figure out how to make it tail | |
recursive, what I'm suggesting is that you write the second one and | |
then try to optimize it to eliminate the function parameter | |
-- TheOnionKnight *) | |
let count'' n = | |
let rec count n ret = | |
match n with | |
0 -> List.rev ret | |
| n -> count (n - 1) (n :: ret) | |
count n [] | |
count 20 | |
count' 20 | |
count'' 20 | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| |
let (|Even|Odd|) n = if n%2 = 0 then Even else Odd | |
let P1 n = | |
match n * (n + 3) with | |
| Even -> true | |
| Odd -> false | |
let P2 n = | |
if n >= 10 then | |
let x = float n | |
if 2. ** x > x ** 3. then true else false | |
else true | |
let P3 n = | |
let x = float n | |
if 2.*(x - 1.) = x ** 2. then true else false | |
// implement algorithm I for these proposition functions on your own | |
open System | |
open System.Collections.Generic | |
let induct prop (s : IEnumerable<_>) = Seq.tryPick (fun x -> if prop (x+1) then None | |
else Some(x)) (Seq.append (seq [-1]) s) | |
induct P1 [0 .. 1000] | |
induct P2 [0 .. 1000] | |
#time | |
let fibs = Seq.unfold (fun (n0, n1) -> Some(n0, (n1, n0+n1))) (0I,1I) | |
fibs |> Seq.nth 45 | |
let phi = (1. + (sqrt 5.)) / 2. | |
(1. + phi = phi ** 2.) | |
let P4 n = | |
if (float (Seq.nth n fibs) <= (phi ** (float (n - 1)))) then true else false | |
induct P4 [0] | |
P4 0 | |
Seq.nth 0 fibs | |
let nthroot n a = | |
let epsilon_float = 2.2204460492503131e-16m | |
let nf = float n in | |
let x = [| a; a / nf |] in | |
while System.Math.Abs(x.[1] - x.[0]) > epsilon_float do | |
x.[0] <- x.[1]; | |
x.[1] <- ((nf - 1.0) * x.[1] + a / (x.[1] ** (nf - 1.0))) / nf; | |
x.[1] | |
let phiM = (1.m + (nthroot 5.m 2) / 2.m) | |
phi |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
namespace BasicConcepts | |
module NumbersPowersLogarithms = | |
let x = () | |
open NumbersPowersLogarithms | |
module Tests = | |
(* not all equations are suitable for code *) | |
let integer = 1 | |
let rational = 1N/2N (* requires powerpack *) | |
let real = 1.123456789 | |
let real' = 0.99999999999 (* equals 1 *) | |
let y = () |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| |
namespace BasicConcepts | |
#r "FSharp.PowerPack.dll" | |
module NumbersPowersLogarithms = | |
let x = () | |
open NumbersPowersLogarithms | |
module Tests = | |
(* not all equations are suitable for code *) | |
let integer = 1 | |
let rational = 1N/2N | |
let real = 1.123456789 | |
let real' = 0.99999999999 (* equals 1 *) | |
let y = () |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
open System | |
let r = new System.Random() | |
let roll () = (r.Next() % 5) + 1 | |
let rolls = seq { for x in 1 .. 144 do yield seq { for x in 1 .. 144 do yield (roll(),roll()) }} | |
rolls |> Seq.take 2 | |
rolls |> Seq.map (fun xs -> Seq.map (fun x -> fst x + snd x) xs) | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?xml version="1.0" encoding="utf-8"?> | |
<Project ToolsVersion="4.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003"> | |
<PropertyGroup> | |
<Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration> | |
<Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform> | |
<ProductVersion>8.0.30703</ProductVersion> | |
<SchemaVersion>2.0</SchemaVersion> | |
<ProjectGuid>{3c9762e2-3a83-4dfd-a7ac-663c17a40df7}</ProjectGuid> | |
<OutputType>Library</OutputType> | |
<RootNamespace>AoCP</RootNamespace> | |
<AssemblyName>AoCP</AssemblyName> | |
<TargetFrameworkVersion>v4.0</TargetFrameworkVersion> | |
<Name>AoCP</Name> | |
</PropertyGroup> | |
<PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' "> | |
<DebugSymbols>true</DebugSymbols> | |
<DebugType>full</DebugType> | |
<Optimize>false</Optimize> | |
<Tailcalls>false</Tailcalls> | |
<OutputPath>bin\Debug\</OutputPath> | |
<DefineConstants>DEBUG;TRACE</DefineConstants> | |
<WarningLevel>3</WarningLevel> | |
<DocumentationFile>bin\Debug\AoCP.XML</DocumentationFile> | |
</PropertyGroup> | |
<PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' "> | |
<DebugType>pdbonly</DebugType> | |
<Optimize>true</Optimize> | |
<Tailcalls>true</Tailcalls> | |
<OutputPath>bin\Release\</OutputPath> | |
<DefineConstants>TRACE</DefineConstants> | |
<WarningLevel>3</WarningLevel> | |
<DocumentationFile>bin\Release\AoCP.XML</DocumentationFile> | |
</PropertyGroup> | |
<Import Project="$(MSBuildExtensionsPath32)\FSharp\1.0\Microsoft.FSharp.Targets" Condition="!Exists('$(MSBuildBinPath)\Microsoft.Build.Tasks.v4.0.dll')" /> | |
<Import Project="$(MSBuildExtensionsPath32)\..\Microsoft F#\v4.0\Microsoft.FSharp.Targets" Condition=" Exists('$(MSBuildBinPath)\Microsoft.Build.Tasks.v4.0.dll')" /> | |
<ItemGroup> | |
<Compile Include="1.1.fsi" /> | |
<Compile Include="1.1.fs" /> | |
<None Include="1.1.fsx" /> | |
<None Include="1.1_usage.fsx" /> | |
<Compile Include="1.2.1.fsi" /> | |
<Compile Include="1.2.1.fs" /> | |
<None Include="1.2.1.fsx" /> | |
<None Include="1.2.1_usage.fsx" /> | |
<None Include="1.2.1_Digression_IntegerPartition_TailRecursion.fsx" /> | |
<None Include="1.2.2.fsx" /> | |
<None Include="1.2.2_usage.fsx" /> | |
<None Include="3.3.1.fsx" /> | |
</ItemGroup> | |
<ItemGroup> | |
<Reference Include="mscorlib" /> | |
<Reference Include="FSharp.Core" /> | |
<Reference Include="System" /> | |
<Reference Include="System.Core" /> | |
<Reference Include="System.Numerics" /> | |
</ItemGroup> | |
<!-- To modify your build process, add your task inside one of the targets below and uncomment it. | |
Other similar extension points exist, see Microsoft.Common.targets. | |
<Target Name="BeforeBuild"> | |
</Target> | |
<Target Name="AfterBuild"> | |
</Target> | |
--> | |
</Project> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment