Blogs

circular definitions in "Monads as Containers"

Submitted by metaperl on Tue, 04/18/2006 - 10:13pm.

We first see

What bind does is to take a container of type (m a) and a function of type (a -> m b). It first maps the function over the container, (which would give an m (m b)) and then applies join to the result to get a container of type (m b).

But then we see

Joining is equivalent to binding a container with the identity map. This is indeed still called join in Haskell:

So then the question becomes: if bind uses join and join uses bind, then we have a serious circularity issue...

Sometimes imperative works out better?

Submitted by metaperl on Tue, 04/18/2006 - 8:45pm.

From the ocaml book we have the following

Certain algorithms are easier to write in this (imperative) programming style. Take for instance the computation of the product of two matrices. Even though it is certainly possible to translate it into a purely functional version, in which lists replace vectors, this is neither natural nor efficient compared to an imperative version.

non-deterministic monad of streams easier in Ocaml?

Submitted by metaperl on Tue, 04/18/2006 - 7:13am.

I was reading Cale Gibbard's Monads as Containers and thought "now this is what I learned Haskell for" and then I began to wonder about Ocaml and monads, which led me to google which led me to this post on non-deterministic monad of streams which the author says "cannot be (naively) done in either Prolog or in Haskell's
|MonadPlus monad, both of which would go into an infinite loop on this example."

oo versus fp : it all boils down to where you get your extensibility

Submitted by metaperl on Tue, 04/18/2006 - 6:45am.

[19:33:05] /Cale/ But in FP, things are usually sort of 'dual' to OO in a strange way. Data is inextensible, but the operations on it are very extensible, which is sort of the reverse of the situation in OO-land.

simply put, but oh so true:

Submitted by metaperl on Sat, 04/15/2006 - 8:29pm.


[19:26:57] /Cale/ loufoque: another thing is that it's just
fun to program in Haskell -- you don't feel so much like
you're writing boilerplate code all the time, and if it
compiles, it usually works, since the typesystem catches
80 or 90 percent of all the stupid mistakes which the
compilers in other languages wouldn't.

how the (m a) of m (m a) can be represent a several containers for a data type

Submitted by metaperl on Fri, 04/14/2006 - 7:30pm.
this is more of a personal blog post than anything, so either you get it or you dont [18:10:44] palomer: but what does return do? [18:12:17] it takes a value of type b and returns a value of type (m b) [18:12:29] a value of type (m b) is a box with value of type b in it [18:14:49] palomer: but that's just my point: (m b) has _one_ element [18:15:12] therefore m (m a) is something where m has (m a) and (m a) has one element [18:18:55] "The third method, join, also specific to monads, takes a container of containers m (m a), and combines them into one m a in some sensible fashion." ---- why is this a container of containers instead of a container of one [18:21:55] @type [True, False, True] [18:21:57] [Bool] [18:22:07] @type [[True, False, True], [False, True]] [18:22:07] [[Bool]] [18:22:15] That's for metaperl . [18:23:39] monochrom: ah! the second one is m (m a) [18:23:55] YES! [18:36:15] return takes a single element and "containerizes it", yielding something of type m a... but that (m a) just so happens to be an (m a) where the container has one element. There is nothing about the notation (m a) which constrains (m a) to only contain one type as the input to join (as well as monochrom's example) shows

analyzing the stringification of a tree data structure

Submitted by metaperl on Tue, 04/11/2006 - 11:24am.

In section 8.3 of the discussion on stringifying tree structures Hudak says:

Because (++) has time complexity linear in the length of its left argument, showTree is potentially quadratic in the size of the tree.

in response to this code:


showTree (Leaf x) = show x
showTree (Branch l r) = "<" ++ showTree l ++ "|" ++ showTree r ++ ">"

So this brings up two questions:

  1. Why does (++) have time complexity linear in the length of its left argument?
  2. Why is showTree potentially quadratic in the size of the tree?

Novice Questions

Submitted by metaperl on Wed, 04/05/2006 - 4:19pm.
For a function fn (x:xs) ... what happens if it is called like this fn []?
An error
A convenient way to alias a type is how?
type String = [Char]

Todo List

Submitted by metaperl on Mon, 04/03/2006 - 9:33am.
  1. A Haskell paste page which syntax highlights Haskell code. Using paste.lisp.org is not a good idea because people don't respond to paste questions listed there

First Post: Cellular Automata Simulator

Submitted by Revision17 on Sun, 04/02/2006 - 7:16pm.

Alright, I'm new to haskell, and I just wrote a cellular automata simlator that a few people have expressed interest in seeing, so here it is:


module Main where
import Data.Bits
import Text.Printf (printf)

newtype State = State ([Bool],Int)

stateLineToString (x:xs) | x == True = 'X':(stateLineToString xs)
			 | otherwise = ' ':(stateLineToString xs)
stateLineToString [] = "|"
instance Show (State) where
	show (State (x,y)) =  printf "%04.0d:%s|" y  (stateLineToString x)


{-
hood = 3 cell neighborhood; this determines which bit of the ruleNumber we look at for the result; it's three least significant bits determine which neighborhood it is
-}
applyRule :: Int -> (Bool,Bool,Bool) -> Bool
applyRule ruleNum hood = testBit ruleNum (tripleToInt hood)

tripleToInt :: (Bool,Bool,Bool) -> Int
tripleToInt (x,y,z) = (x `trueNum` 4) + (y `trueNum` 2) + (z `trueNum` 1)
	where
	trueNum x y | x == True = y
		      | otherwise = 0



applyRuleToState :: ((Bool,Bool,Bool) -> Bool) -> State -> State --  [Bool] -> [Bool]
applyRuleToState  f (State (x,y)) = State (False:(applyRuleToList f x),(y+1))


applyRuleToList :: ((Bool,Bool,Bool) -> Bool) -> [Bool] -> [Bool]
applyRuleToList rule (a:b:c:rest) = (rule (a,b,c)):(applyRuleToList rule (b:c:rest))
applyRuleToList _ [x,y] = [x]



testState = State ((take 100 (repeat False)) ++ [True] ++ (take 100 (repeat False)),0)
test =  applyRuleToState rule30 testState


rule30 = applyRule 30
rule30All = iterate (applyRuleToState rule30) testState

rule90 = applyRule 90
rule90All = iterate (applyRuleToState rule90) testState

rulesToString :: [State] -> String
rulesToString (x:xs) = ((show x) ++ ['\n'])++(rulesToString xs)
rulesToSTring [] = ['\n']


main :: IO ()
main = putStrLn (rulesToString (take 100 rule90All))


As I'm still new there are some sloppy things with it, but it'll output a rule 90 cellular automata. With slight modification, it'll output any that use 3 cell neighborhoods.