In heterogeneous lists, is it possible to make a zip and then unzip equal to the original?
I'm talking about zip operations in the context of heterogeneous lists. I am working on a slightly dependent language that uses them as tuples.
type T =
| S of string
| R of T list
let rec zip l =
let is_all_r_empty x = List.forall (function R [] -> true | _ -> false) x
let rec loop acc_total acc_head acc_tail x =
match x with
| S _ :: _ -> R l
| R [] :: ys ->
if List.isEmpty acc_head && is_all_r_empty ys then List.rev acc_total |> R
else R l
| R (x :: xs) :: ys -> loop acc_total (x :: acc_head) (R xs :: acc_tail) ys
| [] ->
match acc_tail with
| _ :: _ -> loop ((List.rev acc_head |> zip) :: acc_total) [] [] (List.rev acc_tail)
| _ -> List.rev acc_total |> R
loop [] [] [] l
let rec unzip l =
let transpose l =
let is_all_empty x = List.forall (function _ :: _ -> false | _ -> true) x
let rec loop acc_total acc_head acc_tail = function
| (x :: xs) :: ys -> loop acc_total (x :: acc_head) (xs :: acc_tail) ys
| [] :: ys ->
if List.isEmpty acc_head && is_all_empty ys then loop acc_total acc_head acc_tail ys
else l
| [] ->
match acc_tail with
| _ :: _ -> loop (List.rev acc_head :: acc_total) [] [] (List.rev acc_tail)
| _ -> List.rev acc_total
loop [] [] [] l
let is_all_r x = List.forall (function R _ -> true | _ -> false) x
match l with
| R x when is_all_r x -> List.map unzip x |> transpose |> List.map R
| R x -> x
| S _ -> failwith "Unzip called on S."
//let a = R [R [S "a"; S "t"]; R [S "b"; S "w"]; R [S "c"; S "e"]]
//let b = R [R [S "1"; S "4"]; R [S "5"; S "r"]; R [S "3"; S "6"]]
//let c = R [R [S "z"; S "v"]; R [S "x"; S "b"]; R [S "c"; S "2"]]
//
//let t3 = zip [a;b]
//let t4 = zip [t3;c]
//let u1 = unzip t4
//let r1 = u1 = [t3;c]
//let u2 = unzip t3
//let r2 = u2 = [a;b] // The above works fine on tuples with regular dimensions.
let a = R [R [S "q"; S "w"; S "e"]]
let b = R [R [S "a"; S "s"]; R [S "z"]; S "wqe"]
let ab = [a;b]
let t = zip ab
let t' = unzip t
ab = t' // This is false, but I would like the ziping and then unziping to be reversible if possible.
Cropping and unboxing can generally be expressed as a shift in size or a series of transpositions. These are all these two functions.
They behave well on regular tuples, but I would like zip + unzip to be isomorphic on irregular ones. My intuition tells me that this will require too many of them.
I need a second opinion here.
+3
source to share
1 answer
#r "../../packages/FsCheck.2.8.0/lib/net452/FsCheck.dll"
type T =
| S of string
| VV of T list
let transpose l on_fail on_succ =
let is_all_vv_empty x = List.forall (function VV [] -> true | _ -> false) x
let rec loop acc_total acc_head acc_tail = function
| VV [] :: ys ->
if List.isEmpty acc_head && is_all_vv_empty ys then
if List.isEmpty acc_total then failwith "Empty inputs in the inner dimension to transpose are invalid."
else List.rev acc_total |> on_succ
else on_fail ()
| VV (x :: xs) :: ys -> loop acc_total (x :: acc_head) (VV xs :: acc_tail) ys
| _ :: _ -> on_fail ()
| [] ->
match acc_tail with
| _ :: _ -> loop (VV (List.rev acc_head) :: acc_total) [] [] (List.rev acc_tail)
| _ -> List.rev acc_total |> on_succ
loop [] [] [] l
let rec zip l =
match l with
| _ :: _ -> transpose l (fun _ -> l) (List.map (function VV x -> zip x | x -> x)) |> VV
| _ -> failwith "Empty input to zip is invalid."
let rec unzip l =
let is_all_vv x = List.forall (function VV _ -> true | _ -> false) x
match l with
| VV x ->
match x with
| _ :: _ when is_all_vv x -> let t = List.map (unzip >> VV) x in transpose t (fun _ -> x) id
| _ :: _ -> x
| _ -> failwith "Empty inputs to unzip are invalid."
| S _ -> failwith "Unzip called on S."
open FsCheck
open System
let gen_t =
let mutable gen_t = None
let gen_s () = Gen.map S Arb.generate<string>
let gen_vv size = Gen.nonEmptyListOf (gen_t.Value size) |> Gen.map VV
gen_t <-
fun size ->
match size with
| 0 -> gen_s()
| _ when size > 0 -> Gen.oneof [gen_s (); gen_vv (size-1)]
| _ -> failwith "impossible"
|> Some
gen_t.Value
|> Gen.sized
let gen_t_list_irregular = Gen.nonEmptyListOf gen_t
let gen_t_list_regular = Gen.map2 List.replicate (Gen.choose(1,10)) gen_t
type MyGenerators =
static member Tuple() = Arb.fromGen gen_t
static member TupleList() = Arb.fromGen gen_t_list_regular
Arb.register<MyGenerators>()
let zip_and_unzip orig = zip orig |> unzip
let zip_and_unzip_eq_orig orig = zip_and_unzip orig = orig
// For regular tuples it passes with flying colors.
Check.One ({Config.Quick with EndSize = 10}, zip_and_unzip_eq_orig)
// I can't get it to be isomorphic for irregularly sized arrays as expected.
//let f x =
// let x' = zip x
// printfn "x'=%A" x'
// printfn "unzip x'=%A" (unzip x')
// printfn "zip_and_unzip_eq_orig x=%A" (zip_and_unzip_eq_orig x)
//
//f [VV [VV [S "12"; S "qwe"]; VV [S "d"]]; VV [VV [S ""; S "ug"]; VV [S ""]]]
No matter what I try, I can't figure out how to make a pair isomorphic for tuples of the wrong size, and I feel like it's unlikely anyone will tell me otherwise, so I put the above attempt as an answer for now.
At the top, based on the tests above, I'm pretty sure it should be isomorphic across all regular tuples. I think this should be enough. I pulled the code a little bit compared to the example I had in the question.
This irregular unboxing and unboxing problem will create an interesting math puzzle.
+1
source to share