Last active
June 4, 2017 09:55
-
-
Save CarstenKoenig/5bf59aec168d0d895e1be5de22fb777c to your computer and use it in GitHub Desktop.
Recursive Problem / Data
This file contains hidden or 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
| (***************************************************************************************** | |
| * Task: | |
| * ===== | |
| * | |
| * There is a string which may contain asterisks. Each asterisk must be replaced by | |
| * a 0 or 1 and then all possible output combinations must be printed out. | |
| * | |
| * For example the strings | |
| * | |
| * a*b must produce two outputs a0b and a1b | |
| * a**b must produce a00b, a01b, a10b, a11b | |
| * a***b must produce eight outputs a000b,a001b,a010b,a011b,a100b,a101b,a110b,a111b | |
| * A string with 5 asterisks should produce 32 outputs. | |
| **************************************************************************************) | |
| module Main = | |
| type FormatF<'a> = | |
| | FChar of char * 'a | |
| | FStar of 'a | |
| | FEnd | |
| // FormatF is a functor: | |
| let formatMap f = | |
| function | |
| | FChar (c, x) -> FChar (c, f x) | |
| | FStar x -> FStar (f x) | |
| | FEnd -> FEnd | |
| // F-Algebra for the combinations | |
| let combineAlg values = | |
| function | |
| | FEnd -> Seq.singleton "" | |
| | FChar (c, rest) -> | |
| rest | |
| |> Seq.map (fun s -> string c + s) | |
| | FStar rest -> | |
| Seq.allPairs values rest | |
| |> Seq.map (fun (v, r) -> v.ToString() + r) | |
| // stupid Bug on FSI 4.1 on Linux/Mono 5.0.0 | |
| // this one works but if you coment out the (unused) local | |
| // inc definition it produces random (uninitialized) integers | |
| let countAlg = | |
| let inc (n : int) = n + 1 | |
| function | |
| | FEnd -> 0 | |
| | FChar (_, n) -> n | |
| | FStar n -> n+1 | |
| // fixing the type (tying the knot) | |
| type Format = Format of FormatF<Format> | |
| let unwrap (Format format) = format | |
| // the catamorphism | |
| let rec catamorphism unwrap fMap fAlg wrapped = | |
| fAlg (fMap (catamorphism unwrap fMap fAlg) (unwrap wrapped)) | |
| let combine values = | |
| catamorphism unwrap formatMap (combineAlg values) | |
| let countStars format = | |
| catamorphism unwrap formatMap countAlg format | |
| let rec parse (input : string) = | |
| if input.Length = 0 then Format FEnd else | |
| match input.[0] with | |
| | '*' -> FStar (parse input.[1..]) | |
| | c -> FChar (c, parse input.[1..]) | |
| |> Format | |
| let main _ = | |
| let formula = parse "a**b*c" | |
| printfn "with %d stars: " (countStars formula) | |
| formula | |
| |> combine [0; 1] | |
| |> Seq.iter (printfn "%s") | |
| 0 // return an integer exit code | |
| Main.main [||] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment