Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Capture the notion of invertible functions (Kim-Ee Yeoh)
2. Re: Capture the notion of invertible functions (Arjun Comar)
3. Ambiguous type variables (Dennis Raddle)
4. Re: Capture the notion of invertible functions (Kim-Ee Yeoh)
----------------------------------------------------------------------
Message: 1
Date: Mon, 17 Mar 2014 20:28:35 +0700
From: Kim-Ee Yeoh <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Capture the notion of invertible
functions
Message-ID:
<CAPY+ZdQdrk=pqos-pbnno6txt0kx_wljcuhlsfrndtkd+4a...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
Hi Javran,
1. Have you looked at iso lens? The lens library contextualizes
isomorphisms among other interesting maps. Worth looking into.
2. Your code looks nicely idiomatic. You must have worked hard observing
models of good haskell.
3. It's easy to declare at the type-level: a->b and b->a. It's just that
the types don't say anything about whether they are isos or not. Whereas
that's what we want.
Typically when I have such a pair of functions, I lean on quickcheck to
give me a rapid verify as I tweak away, e.g.:
prop_encdecOk :: String -> Bool
prop_encdecOk xs = xs == (decode . encode $ xs)
-- Kim-Ee
On Mon, Mar 17, 2014 at 2:44 PM, Javran Cheng <[email protected]> wrote:
> Hi,
>
> These days I find the notion of "inverse function" might be useful,
> the basic idea is to keep a pair of function f and g which are the inverse
> functions of each other
> and then manipulate on this pair of functions.
>
> The detail is both on my blog post:
>
>
> http://javran.github.io/posts/2014-03-17-capture-the-notion-of-invertible-functions.html
>
> and also code review:
>
>
> http://codereview.stackexchange.com/questions/44550/capture-the-notion-of-invertible-functions
>
> I think this is an interesting idea and want to share it with you.
> Advice and comments are welcomed and appreciated since I learn haskell
> through LYAH and some wiki pages
> and still not sure about what would be the most idiomatic way of doing it
> in haskell.
>
> Thanks,
>
> --
> Javran (Fang) Cheng
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140317/ce1c0786/attachment-0001.html>
------------------------------
Message: 2
Date: Mon, 17 Mar 2014 09:38:19 -0400
From: Arjun Comar <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Capture the notion of invertible
functions
Message-ID:
<cadjrcrv2ehj5v2zf-oycqa5vso+edk0hehhvn5507d3fnsc...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
Adding to Kim-Ee's point,
1) When you're talking about invertible functions, the idea you're probably
reaching for is an isomorphism -- that is, we want the function to have
certain nice properties on top of just being a map from a -> b with an
inverse map from b -> a. You also want the function to be a bijection,
which is captured in the notion of an isomorphism.
2) Iso from Lens composes with the normal function composition operator (.)
instead of rappend -- which is a little more convenient.
Arjun
On Mon, Mar 17, 2014 at 9:28 AM, Kim-Ee Yeoh <[email protected]> wrote:
> Hi Javran,
>
> 1. Have you looked at iso lens? The lens library contextualizes
> isomorphisms among other interesting maps. Worth looking into.
>
> 2. Your code looks nicely idiomatic. You must have worked hard observing
> models of good haskell.
>
> 3. It's easy to declare at the type-level: a->b and b->a. It's just that
> the types don't say anything about whether they are isos or not. Whereas
> that's what we want.
>
> Typically when I have such a pair of functions, I lean on quickcheck to
> give me a rapid verify as I tweak away, e.g.:
>
> prop_encdecOk :: String -> Bool
> prop_encdecOk xs = xs == (decode . encode $ xs)
>
>
> -- Kim-Ee
>
>
> On Mon, Mar 17, 2014 at 2:44 PM, Javran Cheng <[email protected]> wrote:
>
>> Hi,
>>
>> These days I find the notion of "inverse function" might be useful,
>> the basic idea is to keep a pair of function f and g which are the
>> inverse functions of each other
>> and then manipulate on this pair of functions.
>>
>> The detail is both on my blog post:
>>
>>
>> http://javran.github.io/posts/2014-03-17-capture-the-notion-of-invertible-functions.html
>>
>> and also code review:
>>
>>
>> http://codereview.stackexchange.com/questions/44550/capture-the-notion-of-invertible-functions
>>
>> I think this is an interesting idea and want to share it with you.
>> Advice and comments are welcomed and appreciated since I learn haskell
>> through LYAH and some wiki pages
>> and still not sure about what would be the most idiomatic way of doing it
>> in haskell.
>>
>> Thanks,
>>
>> --
>> Javran (Fang) Cheng
>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140317/166dcb25/attachment-0001.html>
------------------------------
Message: 3
Date: Mon, 17 Mar 2014 12:14:31 -0700
From: Dennis Raddle <[email protected]>
To: Haskell Beginners <[email protected]>
Subject: [Haskell-beginners] Ambiguous type variables
Message-ID:
<cakxlvorbko_v9vaba573rdf1zjootlf9duwufls_ecbxa25...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
I need help with an "ambiguous type variables" error.
My problem domain is backtracking search to construct musical phrases by
choosing notes that fulfill as many simultaneous criteria as possible. At
the beginning, I always know that I need to choose N notes, and they will
be chosen in a particular order, one at a time. I don't need to worry about
cycles, therefore. There is a way of calculating a "goodness" score, given
a series of the first M notes (where M ranges from 2 to N). I'm looking for
the solution with the best score. Because my problem may be too large to do
a complete search, I think it would be great to be able to do a combination
of breadth and depth searching... sort of like a chess program that
searches X moves ahead but not all the way to the end of the game. So I
start with 1 note and do a complete search on all partial solutions with X
notes looking for the best score (dealing with ties somehow, not sure yet
how), then take the first note from the best solution, then do a complete
search on all partial solutions with 2 to X+1 notes, and so forth until
X=N.
I have in mind many possible ways of representing phrases and "moves," so I
wanted to implement my basic algorithm in a class. I need three data types:
- "the data" : a representation of a solution with from 1 to N choices
applied
- "a choice" : a representation of a choice of note at a particular point
in the phrase
- "memo" : a way of tracking the best partial solution(s) found during this
phase of the search
Here's my code so far
In the following the type variable "d" is "the data", "c" is "a choice" and
"memo" is a memo.
The error is
Ambiguous type variables 'd0', 'c0' in the constraint:
(Bt d0 c0 memo) arising from a use of 'newMemo'
class Bt d c memo | d -> c, d -> memo where
-- a solution state is checked against the best solutions stored in
-- the memo, and possibly replaces or augments the list of best
-- solutions.
updateMemo :: memo -> d -> memo
newMemo :: memo
pickBest :: Int -> memo -> d
isSolution :: d -> Bool
isSolution x = stateSize x == solutionSize x
-- number of choices applied so far
stateSize :: d -> Int
-- note that data of type 'd' includes an indication of what the
-- final solution size is, something put there when d is initialized
solutionSize :: d -> Int
enumerateChoices :: d -> [c] -- choices available at this point in the
-- construction of the state
-- compute a goodness score
scoreState :: d -> Double
applyChoice :: d -> c -> d
-- note that this is only partially implemented. Never mind that
-- it's not complete or correct, I'm still trying to understand
-- where my error arises.
--
-- What is will eventually do: completely searches N levels deep
-- before picking best score, then takes best partial solution,
-- backs up N-1 levels and does another complete search,
-- etc. finally displays solution with best score.
limBacktrack :: Int -> d -> memo
limBacktrack n d = limBacktrack' n newMemo d
limBacktrack' :: Int -> memo -> d -> memo
limBacktrack' nGoal memo d
| stateSize d == nGoal = updateMemo memo d
| otherwise = foldl g memo (enumerateChoices d)
where
-- g :: memo -> choice -> memo
g memo choice = limBacktrack' nGoal memo (applyChoice d choice)
The error is
Ambiguous type variables 'd0', 'c0' in the constraint:
(Bt d0 c0 memo) arising from a use of 'newMemo'
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140317/d15805e3/attachment-0001.html>
------------------------------
Message: 4
Date: Tue, 18 Mar 2014 02:48:21 +0700
From: Kim-Ee Yeoh <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Capture the notion of invertible
functions
Message-ID:
<CAPY+ZdTyj81gcUaZJfHGeta8rbjxup8ReKHJ=iy7epzkkqp...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
> When you're talking about invertible functions, the idea you're probably
reaching for is an isomorphism -- that is, we want the function to have
certain nice properties on top of just being a map from a -> b with an
inverse map from b -> a.
The usual meaning of 'f is invertible' is that it is both left- and
right-invertible, thus making it bijective: see first bullet in [1].
Here you're alluding to f being merely left-invertible, something I don't
see mentioned in OP.
> You also want the function to be a bijection, which is captured in the
notion of an isomorphism.
I'm reminded of a reddit convo where the idea was tossed out that
semigroups should always be promoted to monoids [2].
I argued no. I also cited a case where a supposedly nicer monoid causes
more problems for a ghc hacker than the true semigroup [3].
Having structure is nice. And sometimes we just have to work with what's
given to us.
Category theory calls a /monomorphism/ something that's strictly weaker
than left-invertible. An arrow that's (additionally) left-invertible
corresponds to a /split mono/.
Hence in order of _decreasing_ niceness: Iso, Split mono, Mono. As research
uncovers more interesting phenomena, this sequence will continuing growing
to the right.
We can't always impose that niceness because that nukes whatever we're
studying. So we gotta respect the situation. And given lemons, make
lemonade.
[1]
http://en.wikipedia.org/wiki/Bijection,_injection_and_surjection#Bijection
[2]
http://www.reddit.com/r/haskell/comments/1ou06l/improving_applicative_donotation/ccvtqot?context=1
[3]
http://www.reddit.com/r/haskell/comments/1ou06l/improving_applicative_donotation/ccy4n2d
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140318/04565dde/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 69, Issue 22
*****************************************
