Is there an elegant way to return functions of a function of the same type (in a tuple)

Question

I use haskell to implement a template that includes functions that return a value and myself (or a function of the same type). Right now I implemented it like this:

newtype R a = R (a , a -> R a) -- some toy functions to demonstrate alpha :: String -> R String alpha str | str == reverse str = R (str , omega) | otherwise = R (reverse str , alpha) omega :: String -> R String omega (s:t:r) | s == t = R (s:t:r , alpha) | otherwise = R (s:s:t:r , omega) 

The driving force for these types of functions is a function called a cascade:

 cascade :: (a -> R a) -> [a] -> [a] cascade _ [] = [] cascade f (l:ls) = el : cascade g ls where R (el , g) = fl 

Which takes the initial function and the list and returns the list created by the application of the seed function to the first element of the list, applying the function returned by this to the second element of the list, and so on and so forth.

This works - however, in the process of using this for a little more useful things, I noticed that many times I had basic units, of which functions that returned functions other than themselves were rare; and explicitly declaring a function to regain itself became somewhat tedious. I would rather use something like a Monad return function, however I have no idea what bind will do for functions of these types, especially since I never assumed that they are connected to anything except the function they return to the first turn.

Trying to curb this to the Monad, I began to worry about whether what I was doing was useful or not, so, in short, I want to know:

• Is this what I'm doing bad thing? if not,
• What am I doing before, am I reinventing the wheel again? if not,
• Is there an elegant way to do this, or have I already achieved this, and am I greedy, wanting some sort of return analogue?

(By the way, besides the "functions that return topics" or the "recursive data (functions) structure", I’m not quite sure what this type of template is called, and tried to make effective research difficult in it - If someone could give me a name for of this template (if there really is one), this in itself would be very useful)

Answer 1

As a high-level consideration, I would say that your type is a state-transformed stream transformer. Something a little confusing here is that your type is defined as

 newtype R a = R (a , a -> R a) 

instead

 newtype R a = R (a -> (R a, a)) 

which would be a little more natural in a streaming context, because you usually don’t produce anything if you haven’t received anything yet. Then your functions will also have simpler types:

 alpha, omage :: R String cascade :: R a -> [a] -> [a] 

If we try to generalize this idea of ​​a flow transformer, we will soon realize that the case when we convert list a to list a is just a special case. With the right infrastructure, we could also make a list of b s. Therefore, we are trying to generalize the type of R :

 newtype R ab = R (a -> (R ab, b)) 

I saw a structure called Circuit , which turns out to be a full-blown arrow . Arrows are a generalization of the concept of functions and are an even more powerful construction than monads. I can't pretend to understand theoretical theory, but it's definitely fun to play with them. For example, the trivial conversion is simply Cat.id :

 import Control.Category import Control.Arrow import Prelude hiding ((.), id) import qualified Data.List as L -- ... Definition of Circuit and instances cascade :: Circuit ab -> [a] -> [b] cascade cir = snd . L.mapAccumL unCircuit cir -- ghci> cascade (Cat.id) [1,2,3,4] [1,2,3,4] 

We can also model the state by parameterizing the circuit, which we return as a continuation:

 countingCircuit :: (a -> b) -> Circuit a (Int, b) countingCircuit f = cir 0 where cir i = Circuit $ \x -> (cir (i+1), (i, fx)) -- ghci> cascade (countingCircuit (+5)) [10,3,2,11] [(0,15),(1,8),(2,7),(3,16)] 

And the fact that our schema type is a category gives us a good way to create schemas:

 ghci> cascade (countingCircuit (+5) . arr (*2)) [10,3,2,11] [(0,25),(1,11),(2,9),(3,27)] 

Answer 2

It looks like you have a simplified version of the stream. That is, say, a representation of an infinite stream of values. I don’t think you can easily define this as a monad, because you use the same type for your seed as for your elements, which makes it difficult to define fmap (it seems that you will need to invert the function provided in fmap in order to have the ability to restore seeds). You can make this a monad by creating a seed type regardless of the type of element, such as

 {-# LANGUAGE ExistentialQuantification #-} data Stream a = forall s. Stream as (s -> Stream a) 

This will allow you to define an instance of Functor and Monad as follows

 unfold :: (b -> (a, b)) -> b -> Stream a unfold fb = Stream ab' (unfold f) where (a, b') = fb shead :: Stream a -> a shead (Stream a _ _) = a stail :: Stream a -> Stream a stail (Stream _ bf) = fb diag :: Stream (Stream a) -> Stream a diag = unfold f where f str = (shead $ shead str, stail $ fmap stail str) sjoin :: Stream (Stream a) -> Stream a sjoin = diag instance Functor Stream where fmap f (Stream abg) = Stream (fa) b (fmap f . g) instance Monad Stream where return = unfold (\x -> (x, x)) xs >>= f = diag $ fmap f xs 

Please note that this only obeys the laws of the Monad, if you consider them as a set, since it does not preserve the order of the elements.

This flow monad explanation uses endless lists that work just as well in Haskell as they can be generated in a lazy way. If you check the documentation for Stream in the vector library, you will find a more complex version so that it can be used to efficiently merge streams.

Answer 3

I have nothing to add, except that your cascade function can be written as the left fold (and therefore also the right fold, although I did not do the conversion).

 cascade f = reverse . fst . foldl func ([], f) where func (rs,g) s = let R (r,h) = gs in (r:rs,h)